結果
問題 | No.1302 Random Tree Score |
ユーザー |
![]() |
提出日時 | 2020-11-28 01:31:57 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 266 ms / 3,000 ms |
コード長 | 2,229 bytes |
コンパイル時間 | 356 ms |
コンパイル使用メモリ | 82,308 KB |
実行使用メモリ | 102,400 KB |
最終ジャッジ日時 | 2024-09-12 21:39:57 |
合計ジャッジ時間 | 4,458 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
import sysp, g, ig = 998244353, 3, 332748118W = [pow(g, (p - 1) >> i, p) for i in range(24)]iW = [pow(ig, (p - 1) >> i, p) for i in range(24)]def fft(k, f):for l in range(k, 0, -1):d = 1 << l - 1U = [1]for i in range(d):U.append(U[-1] * W[l] % p)for i in range(1 << k - l):for j in range(d):s = i * 2 * d + jf[s], f[s+d] = (f[s] + f[s+d]) % p, U[j] * (f[s] - f[s+d]) % pdef ifft(k, f):for l in range(1, k + 1):d = 1 << l - 1for i in range(1 << k - l):u = 1for j in range(i * 2 * d, (i * 2 + 1) * d):f[j+d] *= uf[j], f[j+d] = (f[j] + f[j+d]) % p, (f[j] - f[j+d]) % pu = u * iW[l] % pdef convolve(a, b):n0 = len(a) + len(b) - 1k = (n0).bit_length()n = 1 << ka = a + [0] * (n - len(a))b = b + [0] * (n - len(b))fft(k, a), fft(k, b)for i in range(n):a[i] = a[i] * b[i] % pifft(k, a)invn = pow(n, p - 2, p)for i in range(n0):a[i] = a[i] * invn % pdel a[n0:]return aMOD = p#MOD = 998244353def mul(a, b):return ((a % MOD) * (b % MOD)) % MODdef div(a, b):return mul(a, pow(b, MOD-2, MOD))def div2(a, b):return mul(a, modinv(b))def modinv(a):b, u, v = MOD, 1, 0while b:t = a//ba, u = a-t*b, u-t*va, b, u, v = b, a, v, uu %= MODreturn udef frac(limit):frac = [1]*limitfor i in range(2,limit):frac[i] = i * frac[i-1]%MODfraci = [None]*limitfraci[-1] = pow(frac[-1], MOD -2, MOD)for i in range(-2, -limit-1, -1):fraci[i] = fraci[i+1] * (limit + i + 1) % MODreturn frac, fracifrac, fraci = frac(100001)def cmb(a, b):if not a >= b >= 0:return 0return frac[a]*fraci[b]*fraci[a-b]%MODN, = map(int, input().split())F = [0]*NG = [0]*NG[0] = 1for i in range(N-1):G[i+1] = G[i]*N%MOD#print(G)for i in range(N):F[i] = cmb(N, i)G[i] = G[i]* div2(1, frac[i]) % MOD#print(F)#print(G)H = convolve(F, G)#print(H)R = div2(frac[N-2], pow(N, N-2, MOD))*H[N-2]%MODprint(R)