結果
| 問題 | No.2004 Incremental Coins |
| ユーザー |
 vwxyz
|
| 提出日時 | 2023-05-23 18:37:47 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
AC
|
| 実行時間 | 1,446 ms / 2,000 ms |
| コード長 | 10,084 bytes |
| コンパイル時間 | 392 ms |
| コンパイル使用メモリ | 81,896 KB |
| 実行使用メモリ | 366,004 KB |
| 最終ジャッジ日時 | 2024-11-18 21:11:19 |
| 合計ジャッジ時間 | 20,958 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 2 |
| other | AC * 20 |
ソースコード
import sysreadline=sys.stdin.readlinefrom collections import dequemod = 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 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 Extended_Euclid(n,m):stack=[]while m:stack.append((n,m))n,m=m,n%mif n>=0:x,y=1,0else:x,y=-1,0for i in range(len(stack)-1,-1,-1):n,m=stack[i]x,y=y,x-(n//m)*yreturn x,yclass MOD:def __init__(self,p,e=None):self.p=pself.e=eif self.e==None:self.mod=self.pelse:self.mod=self.p**self.edef Pow(self,a,n):a%=self.modif n>=0:return pow(a,n,self.mod)else:#assert math.gcd(a,self.mod)==1x=Extended_Euclid(a,self.mod)[0]return pow(x,-n,self.mod)def Build_Fact(self,N):assert N>=0self.factorial=[1]if self.e==None:for i in range(1,N+1):self.factorial.append(self.factorial[-1]*i%self.mod)else:self.cnt=[0]*(N+1)for i in range(1,N+1):self.cnt[i]=self.cnt[i-1]ii=iwhile ii%self.p==0:ii//=self.pself.cnt[i]+=1self.factorial.append(self.factorial[-1]*ii%self.mod)self.factorial_inve=[None]*(N+1)self.factorial_inve[-1]=self.Pow(self.factorial[-1],-1)for i in range(N-1,-1,-1):ii=i+1while ii%self.p==0:ii//=self.pself.factorial_inve[i]=(self.factorial_inve[i+1]*ii)%self.moddef Build_Inverse(self,N):self.inverse=[None]*(N+1)assert self.p>Nself.inverse[1]=1for n in range(2,N+1):if n%self.p==0:continuea,b=divmod(self.mod,n)self.inverse[n]=(-a*self.inverse[b])%self.moddef Inverse(self,n):return self.inverse[n]def Fact(self,N):if N<0:return 0retu=self.factorial[N]if self.e!=None and self.cnt[N]:retu*=pow(self.p,self.cnt[N],self.mod)%self.modretu%=self.modreturn retudef Fact_Inve(self,N):if self.e!=None and self.cnt[N]:return Nonereturn self.factorial_inve[N]def Comb(self,N,K,divisible_count=False):if K<0 or K>N:return 0retu=self.factorial[N]*self.factorial_inve[K]%self.mod*self.factorial_inve[N-K]%self.modif self.e!=None:cnt=self.cnt[N]-self.cnt[N-K]-self.cnt[K]if divisible_count:return retu,cntelse:retu*=pow(self.p,cnt,self.mod)retu%=self.modreturn retuN,K=map(int,readline().split())A=list(map(int,readline().split()))P=list(map(int,readline().split()))child=[[] for x in range(N+1)]for i in range(1,N+1):child[P[i-1]].append(i)dp=[deque([]) for x in range(N+1)]MD=MOD(mod)MD.Build_Fact(N+1)fact=1poly_K=[]for i in range(N+1):poly_K.append(fact*MD.Fact_Inve(i)%mod)fact*=K-ifact%=modfor x in range(N,-1,-1):if child[x]:ma=max(len(dp[y]) for y in child[x])for y in child[x]:if len(dp[y])==ma:yy=ybreakdp[x]=dp[yy]for y in child[x]:if y==yy:continuefor i in range(len(dp[y])):dp[x][i]+=dp[y][i]dp[x][i]%=moddp[x].appendleft(A[x])ans_lst=[None]*(N+1)DP=[None]*(N+1)le=len(dp[0])DP[0]=deque(convolution(list(dp[0]),list(poly_K[:le][::-1]))[le-1:])for x in range(N+1):ans_lst[x]=DP[x].popleft()for y in child[x]:if dp[x] is dp[y]:DP[y]=DP[x]else:le=len(dp[y])DP[y]=deque(convolution(list(dp[y]),list(poly_K[:le][::-1]))[le-1:])for i in range(le):DP[x][i]-=DP[y][i]DP[x][i]%=modprint(*ans_lst,sep="\n")