結果
問題 |
No.827 総神童数
|
ユーザー |
|
提出日時 | 2020-12-22 13:27:06 |
言語 | PyPy3 (7.3.15) |
結果 |
TLE
|
実行時間 | - |
コード長 | 1,110 bytes |
コンパイル時間 | 330 ms |
コンパイル使用メモリ | 82,560 KB |
実行使用メモリ | 145,640 KB |
最終ジャッジ日時 | 2024-09-21 14:09:30 |
合計ジャッジ時間 | 6,123 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 6 TLE * 1 -- * 29 |
ソースコード
from collections import deque p = 10**9+7 def pow(x,m): if m==0: return 1 if m==1: return x if m%2==0: return (pow(x,m//2)**2)%p else: return (x*(pow(x,(m-1)//2)**2)%p)%p N = int(input()) B1 = [1 for _ in range(N+1)] for i in range(2,N+1): B1[i]=(B1[i-1]*i)%p B2 = [1 for _ in range(N+1)] B2[N] = pow(B1[N],p-2) for i in range(N-1,1,-1): B2[i]=(B2[i+1]*(i+1))%p def f(n,k): if k>n or k<0: return 0 if k==0 or k==n: return 1 return (B1[n]*B2[k]*B2[n-k])%p G = {i:[] for i in range(1,N+1)} for _ in range(N-1): u,v = map(int,input().split()) G[u].append(v) G[v].append(u) que = deque([(1,0)]) A = [-1 for _ in range(N+1)] A[1]=0 while que: x,d = que.popleft() for y in G[x]: if A[y]<0: A[y]=d+1 que.append((y,d+1)) C = {d:0 for d in range(N)} for i in range(1,N+1): C[A[i]] += 1 tot = 0 for d in range(1,N): if C[d]==0:break cnt = 0 for k in range(1,N+1): cnt = (cnt+f(k-1,d)*B1[d]*B1[N-d-1])%p tot = (tot+C[d]*cnt)%p tot = (tot+B1[N])%p print(tot)