結果

問題 No.827 総神童数
コンテスト
ユーザー silversmith
提出日時 2019-05-14 00:04:29
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 485 ms / 2,000 ms
コード長 867 bytes
コンパイル時間 197 ms
コンパイル使用メモリ 81,968 KB
実行使用メモリ 105,984 KB
最終ジャッジ日時 2024-07-08 11:30:52
合計ジャッジ時間 11,658 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 36
権限があれば一括ダウンロードができます

ソースコード

diff # 

N = int(input())
prime = 10**9 + 7
f = [1] * (N + 1)
for i in range(1, N + 1):
    f[i] = i * f[i-1] % prime
f[0] =f[N]

def inv(x,prime):
    _x = x
    inv = 1
    k = prime -2
    while k > 0:
        if k % 2 == 1:
            inv = (inv * _x) % prime
        _x = (_x * _x) % prime   
        k = int(k /2)
    return inv

#for i in range(1,N+1):
#    f[i] = f[0] * inv(i, prime) % prime
f = [f[0] * inv(i,prime) for i in range(N+1)]

a = [0] * (N + 1)
flag = [False] * (N+1)

edge = [[] for _ in range(N + 1)]
for _ in range(N-1):
    u, v = map(int, input().split())
    edge[u].append(v)
    edge[v].append(u)

q = [1]
a[1] = 1
while len(q) > 0:
    v = q.pop()
    flag[v] = True
    for child in edge[v]:
        if flag[child] == False:
            q.append(child)
            a[child] = a[v] + 1

print(int(sum([f[a[i]] for i in range(1, N+1)])) % prime)
0