結果
問題 | No.1302 Random Tree Score |
ユーザー |
|
提出日時 | 2023-05-30 16:55:22 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 522 ms / 3,000 ms |
コード長 | 10,766 bytes |
コンパイル時間 | 1,663 ms |
コンパイル使用メモリ | 81,792 KB |
実行使用メモリ | 140,320 KB |
最終ジャッジ日時 | 2024-12-28 12:07:43 |
合計ジャッジ時間 | 7,008 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 14 |
ソースコード
import sysinput = lambda :sys.stdin.readline()[:-1]ni = lambda :int(input())na = lambda :list(map(int,input().split()))yes = lambda :print("yes");Yes = lambda :print("Yes");YES = lambda : print("YES")no = lambda :print("no");No = lambda :print("No");NO = lambda : print("NO")#######################################################################mod = 998244353imag = 911660635iimag = 86583718rate2 = (911660635, 509520358, 369330050, 332049552, 983190778, 123842337, 238493703, 975955924, 603855026, 856644456, 131300601,842657263, 730768835, 942482514, 806263778, 151565301, 510815449, 503497456, 743006876, 741047443, 56250497, 867605899)irate2 = (86583718, 372528824, 373294451, 645684063, 112220581, 692852209, 155456985, 797128860, 90816748, 860285882, 927414960,354738543, 109331171, 293255632, 535113200, 308540755, 121186627, 608385704, 438932459, 359477183, 824071951, 103369235)rate3 = (372528824, 337190230, 454590761, 816400692, 578227951, 180142363, 83780245, 6597683, 70046822, 623238099,183021267, 402682409, 631680428, 344509872, 689220186, 365017329, 774342554, 729444058, 102986190, 128751033, 395565204)irate3 = (509520358, 929031873, 170256584, 839780419, 282974284, 395914482, 444904435, 72135471, 638914820, 66769500,771127074, 985925487, 262319669, 262341272, 625870173, 768022760, 859816005, 914661783, 430819711, 272774365, 530924681)def butterfly(a):n = len(a)h = (n - 1).bit_length()len_ = 0while len_ < h:if h - len_ == 1:p = 1 << (h - len_ - 1)rot = 1for s in range(1 << len_):offset = s << (h - len_)for i in range(p):l = a[i + offset]r = a[i + offset + p] * rot % moda[i + offset] = (l + r) % moda[i + offset + p] = (l - r) % modif s + 1 != 1 << len_:rot *= rate2[(~s & -~s).bit_length() - 1]rot %= modlen_ += 1else:p = 1 << (h - len_ - 2)rot = 1for s in range(1 << len_):rot2 = rot * rot % modrot3 = rot2 * rot % modoffset = s << (h - len_)for i in range(p):a0 = a[i + offset]a1 = a[i + offset + p] * rota2 = a[i + offset + p * 2] * rot2a3 = a[i + offset + p * 3] * rot3a1na3imag = (a1 - a3) % mod * imaga[i + offset] = (a0 + a2 + a1 + a3) % moda[i + offset + p] = (a0 + a2 - a1 - a3) % moda[i + offset + p * 2] = (a0 - a2 + a1na3imag) % moda[i + offset + p * 3] = (a0 - a2 - a1na3imag) % modif s + 1 != 1 << len_:rot *= rate3[(~s & -~s).bit_length() - 1]rot %= modlen_ += 2def butterfly_inv(a):n = len(a)h = (n - 1).bit_length()len_ = hwhile len_:if len_ == 1:p = 1 << (h - len_)irot = 1for s in range(1 << (len_ - 1)):offset = s << (h - len_ + 1)for i in range(p):l = a[i + offset]r = a[i + offset + p]a[i + offset] = (l + r) % moda[i + offset + p] = (l - r) * irot % modif s + 1 != (1 << (len_ - 1)):irot *= irate2[(~s & -~s).bit_length() - 1]irot %= modlen_ -= 1else:p = 1 << (h - len_)irot = 1for s in range(1 << (len_ - 2)):irot2 = irot * irot % modirot3 = irot2 * irot % modoffset = s << (h - len_ + 2)for i in range(p):a0 = a[i + offset]a1 = a[i + offset + p]a2 = a[i + offset + p * 2]a3 = a[i + offset + p * 3]a2na3iimag = (a2 - a3) * iimag % moda[i + offset] = (a0 + a1 + a2 + a3) % moda[i + offset + p] = (a0 - a1 + a2na3iimag) * irot % moda[i + offset + p * 2] = (a0 + a1 - a2 - a3) * irot2 % moda[i + offset + p * 3] = (a0 - a1 - a2na3iimag) * irot3 % modif s + 1 != (1 << (len_ - 2)):irot *= irate3[(~s & -~s).bit_length() - 1]irot %= modlen_ -= 2def integrate(a):a=a.copy()n = len(a)assert n > 0a.pop()a.insert(0, 0)inv = [1, 1]for i in range(2, n):inv.append(-inv[mod%i] * (mod//i) % mod)a[i] = a[i] * inv[i] % modreturn adef differentiate(a):n = len(a)assert n > 0for i in range(2, n):a[i] = a[i] * i % moda.pop(0)a.append(0)return adef convolution_naive(a, b):n = len(a)m = len(b)ans = [0] * (n + m - 1)if n < m:for j in range(m):for i in range(n):ans[i + j] = (ans[i + j] + a[i] * b[j]) % modelse:for i in range(n):for j in range(m):ans[i + j] = (ans[i + j] + a[i] * b[j]) % modreturn ansdef convolution_ntt(a, b):a = a.copy()b = b.copy()n = len(a)m = len(b)z = 1 << (n + m - 2).bit_length()a += [0] * (z - n)butterfly(a)b += [0] * (z - m)butterfly(b)for i in range(z):a[i] = a[i] * b[i] % modbutterfly_inv(a)a = a[:n + m - 1]iz = pow(z, mod - 2, mod)for i in range(n + m - 1):a[i] = a[i] * iz % modreturn adef convolution_square(a):a = a.copy()n = len(a)z = 1 << (2 * n - 2).bit_length()a += [0] * (z - n)butterfly(a)for i in range(z):a[i] = a[i] * a[i] % modbutterfly_inv(a)a = a[:2 * n - 1]iz = pow(z, mod - 2, mod)for i in range(2 * n - 1):a[i] = a[i] * iz % modreturn adef convolution(a, b):"""It calculates (+, x) convolution in mod 998244353.Given two arrays a[0], a[1], ..., a[n - 1] and b[0], b[1], ..., b[m - 1],it calculates the array c of length n + m - 1, defined by> c[i] = sum(a[j] * b[i - j] for j in range(i + 1)) % 998244353.It returns an empty list if at least one of a and b are empty.Complexity----------> O(n log n), where n = len(a) + len(b)."""n = len(a)m = len(b)if n == 0 or m == 0:return []if min(n, m) <= 60:return convolution_naive(a, b)if a is b:return convolution_square(a)return convolution_ntt(a, b)def inverse(a):n = len(a)assert n > 0 and a[0] != 0res = [pow(a[0], mod - 2, mod)]m = 1while m < n:f = a[:min(n,2*m)] + [0]*(2*m-min(n,2*m))g = res + [0]*mbutterfly(f)butterfly(g)for i in range(2*m):f[i] = f[i] * g[i] % modbutterfly_inv(f)f = f[m:] + [0]*mbutterfly(f)for i in range(2*m):f[i] = f[i] * g[i] % modbutterfly_inv(f)iz = pow(2*m, mod-2, mod)iz = (-iz*iz) % modfor i in range(m):f[i] = f[i] * iz % modres += f[:m]m <<= 1return res[:n]def log(a):a = a.copy()n = len(a)assert n > 0 and a[0] == 1a_inv = inverse(a)a=differentiate(a)a = convolution(a, a_inv)[:n]a=integrate(a)return adef exp(a):a = a.copy()n = len(a)assert n > 0 and a[0] == 0g = [1]a[0] = 1h_drv = a.copy()h_drv=differentiate(h_drv)m = 1while m < n:f_fft = a[:m] + [0] * mbutterfly(f_fft)if m > 1:_f = [f_fft[i] * g_fft[i] % mod for i in range(m)]butterfly_inv(_f)_f = _f[m // 2:] + [0] * (m // 2)butterfly(_f)for i in range(m):_f[i] = _f[i] * g_fft[i] % modbutterfly_inv(_f)_f = _f[:m//2]iz = pow(m, mod - 2, mod)iz *= -iziz %= modfor i in range(m//2):_f[i] = _f[i] * iz % modg.extend(_f)t = a[:m]t=differentiate(t)r = h_drv[:m - 1]r.append(0)butterfly(r)for i in range(m):r[i] = r[i] * f_fft[i] % modbutterfly_inv(r)im = pow(-m, mod - 2, mod)for i in range(m):r[i] = r[i] * im % modfor i in range(m):t[i] = (t[i] + r[i]) % modt = [t[-1]] + t[:-1]t += [0] * mbutterfly(t)g_fft = g + [0] * (2 * m - len(g))butterfly(g_fft)for i in range(2 * m):t[i] = t[i] * g_fft[i] % modbutterfly_inv(t)t = t[:m]i2m = pow(2 * m, mod - 2, mod)for i in range(m):t[i] = t[i] * i2m % modv = a[m:min(n, 2 * m)]v += [0] * (m - len(v))t = [0] * (m - 1) + t + [0]t=integrate(t)for i in range(m):v[i] = (v[i] - t[m + i]) % modv += [0] * mbutterfly(v)for i in range(2 * m):v[i] = v[i] * f_fft[i] % modbutterfly_inv(v)v = v[:m]i2m = pow(2 * m, mod - 2, mod)for i in range(m):v[i] = v[i] * i2m % modfor i in range(min(n - m, m)):a[m + i] = v[i]m *= 2return adef power(a,k):n = len(a)assert n>0if k==0:return [1]+[0]*(n-1)l = 0while l < len(a) and not a[l]:l += 1if l * k >= n:return [0] * nic = pow(a[l], mod - 2, mod)pc = pow(a[l], k, mod)a = log([a[i] * ic % mod for i in range(l, len(a))])for i in range(len(a)):a[i] = a[i] * k % moda = exp(a)for i in range(len(a)):a[i] = a[i] * pc % moda = [0] * (l * k) + a[:n - l * k]return amod = 998244353nn = 10**6fact = [1] * nnfor i in range(nn - 1):fact[i + 1] = fact[i] * (i + 1) % modinvfact = [1] * nninvfact[nn - 1] = pow(fact[nn - 1], mod - 2, mod)for i in range(nn - 1)[::-1]:invfact[i] = invfact[i + 1] * (i + 1) % moddef binom(x, y):if x < 0 or y < 0 or x - y < 0:return 0return fact[x] * invfact[y] % mod * invfact[x - y] % modn = ni()f = [0] * (n-1)for i in range(n-1):f[i] = (i+1) * invfact[i]f[i] %= modr = power(f, n)s = pow(pow(n,n-2,mod),mod-2,mod)print(r[-1]*fact[n-2]%mod*s%mod)