結果
問題 |
No.827 総神童数
|
ユーザー |
![]() |
提出日時 | 2022-11-20 23:19:59 |
言語 | Python3 (3.13.1 + numpy 2.2.1 + scipy 1.14.1) |
結果 |
TLE
|
実行時間 | - |
コード長 | 718 bytes |
コンパイル時間 | 85 ms |
コンパイル使用メモリ | 12,672 KB |
実行使用メモリ | 101,888 KB |
最終ジャッジ日時 | 2024-09-21 19:55:23 |
合計ジャッジ時間 | 44,641 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 28 TLE * 8 |
ソースコード
import sys sys.setrecursionlimit(10**8) mod = 10**9+7 N = int(input()) G = [list() for _ in range(N)] for i in range(N-1): u, v = map(int,input().split()) u-=1;v-=1 G[u].append(v) G[v].append(u) fac = [0]*(N+1) inv = [0]*(N+1) fac[0]=1;inv[0]=1 for i in range(1,N+1): fac[i] = (fac[i-1]*i)%mod inv[i] = (inv[i-1]*pow(i,mod-2,mod))%mod def ncr(r): return (fac[N]*inv[r]*inv[N-r])%mod res = (N*fac[N-1])%mod depth = [0]*N depth[0] = 1 def dfs(v,p): for nex in G[v]: if nex==p: continue depth[nex] = depth[v]+1 global res res += ncr(depth[nex])*fac[depth[nex]-1]*fac[N-depth[nex]] res %= mod dfs(nex,v) dfs(0,-1) print(res)