結果
問題 |
No.3169 [Cherry 7th Tune] Desire for Approval
|
ユーザー |
👑 ![]() |
提出日時 | 2023-10-29 02:19:39 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 4,267 ms / 7,000 ms |
コード長 | 18,541 bytes |
コンパイル時間 | 699 ms |
コンパイル使用メモリ | 82,400 KB |
実行使用メモリ | 152,756 KB |
最終ジャッジ日時 | 2025-05-30 21:04:13 |
合計ジャッジ時間 | 56,607 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 46 |
ソースコード
""" Mod はグローバル変数からの指定とする. """ """ 積 """ def product_modulo(*X): y=1 for x in X: y=(x*y)%Mod return y """ 階乗 """ def Factor(N): """ 0!, 1!, ..., N! (mod Mod) を出力する. N: int """ f=[1]*(N+1) for k in range(1,N+1): f[k]=(k*f[k-1])%Mod return f def Factor_with_inverse(N): """ 0!, 1!, ..., N!, (0!)^-1, (1!)^-1, ..., (N!)^-1 を出力する. N: int """ f = Factor(N) g = [0]*(N+1) N = min(N, Mod-1) g[N] = pow(f[N], Mod - 2, Mod) for k in range(N-1,-1,-1): g[k] = ((k+1) * g[k+1]) % Mod return f, g def Double_Factor(N): """ 0!!, 1!!, ..., N!! (mod Mod) を出力する. N: int """ f=[1]*(N+1) for i in range(2,N+1): f[i]=i*f[i-2]%Mod return f def Modular_Inverse(N): """ 1^(-1), 2^(-1), ..., N^(-1) (mod Mod) を出力する. [Input] N:int [Output] [-1, 1^(-1), 2^(-1), ..., N^(-1)] (第 0 要素に注意!!) """ inv=[1]*(N+1); inv[0]=-1 for k in range(2, N+1): q,r=divmod(Mod,k) inv[k]=(-q*inv[r])%Mod return inv """ 組み合わせの数 Factor_with_inverse で fact, fact_inv を既に求めていることが前提 (グローバル変数) """ def nCr(n,r): """ nCr (1,2,...,n から相異なる r 個の整数を選ぶ方法) を求める. n,r: int """ if 0<=r<=n: return fact[n]*(fact_inv[r]*fact_inv[n-r]%Mod)%Mod else: return 0 def nPr(n,r): """ nPr (1,2,...,n から相異なる r 個の整数を選び, 並べる方法) を求める. n,r: int """ if 0<=r<=n: return (fact[n]*fact_inv[n-r])%Mod else: return 0 def nHr(n,r): """ nHr (1,2,...,n から重複を許して r 個の整数を選ぶ方法) を求める. n,r: int ※ fact, fact_inv は第 n+r-1 項まで必要 """ if n==r==0: return 1 else: return nCr(n+r-1,r) def Multinomial_Coefficient(*K): """ K=[k_0,...,k_{r-1}] に対して, k_0, ..., k_{r-1} に対する多項係数を求める. k_i: int """ N=0 g_inv=1 for k in K: N+=k g_inv*=fact_inv[k]; g_inv%=Mod return (fact[N]*g_inv)%Mod def Binomial_Coefficient_Modulo_List(n: int): """ n を固定し, r=0,1,...,n としたときの nCr (mod Mod) のリストを出力する. n: int [出力] [nC0 , nC1 ,..., nCn] """ L=[1]*(n+1) inv=Modular_Inverse(n+1) for r in range(1, n+1): L[r]=((n+1-r)*inv[r]%Mod)*L[r-1]%Mod return L def Pascal_Triangle(N: int, mode=False): """ 0<=n<=N, 0<=r<=n の全てに対して nCr (mod M) のリストを出力する. N: int [出力] [[0C0], [1C0, 1C1], ... , [nC0, ... , nCn], ..., [NC0, ..., NCN]] """ if mode: L=[[0]*(N+1) for _ in range(N+1)] L[0][0]=1 for n in range(1,N+1): Ln=L[n]; Lnn=L[n-1] Ln[0]=1 for r in range(1,N+1): Ln[r]=(Lnn[r]+Lnn[r-1])%Mod return L else: X=[1] L=[[1]] for n in range(N): Y=[1] for k in range(1, n+1): Y.append((X[k]+X[k-1])%Mod) Y.append(1) X=Y L.append(Y) return L def Lucas_Combination(n, r): """ Lucas の定理を用いて nCr (mod Mod) を求める. """ X=1 while n or r: ni=n%Mod; ri=r%Mod n//=Mod; r//=Mod if ni<ri: return 0 beta=fact_inv[ri]*fact_inv[ni-ri]%Mod X*=(fact[ni]*beta)%Mod X%=Mod return X """ 特別な数 """ def Catalan_Number(N): """ Catalan 数 C(N) を求める. 注意 C(N)=(2N)!/((N+1)!N!) なので, (2N)! までの値が必要. """ g_inv=fact_inv[N+1]*fact_inv[N]%Mod return fact[2*N]*g_inv%Mod """ 等比数列 """ def Geometric_Sequence(a, r, N): """ k=0,1,...,N に対する a*r^k を出力する. a,r,N: int """ a%=Mod; r%=Mod X=[0]*(N+1); X[0]=a for k in range(1,N+1): X[k]=r*X[k-1]%Mod return X def Geometric_Inverse_Sequence(a, r, N): """ k=0,1,...,N に対する a/r^k を出力する. a,r,N: int """ a %= Mod; r_inv = pow(r, Mod - 2, Mod) X = [0] * (N+1); X[0]=a for k in range(1,N+1): X[k] = r_inv * X[k-1] % Mod return X """ 積和 """ def Sum_of_Product(*X): """ 長さが等しいリスト X_1, X_2, ..., X_k に対して, sum(X_1[i]*X_2[i]*...*X_k[i]) を求める. """ S=0 for alpha in zip(*X): S+=product_modulo(*alpha) return S%Mod def Sum_of_Product_Yielder(N,*Y): S=0 M=len(Y) for _ in range(N+1): x=1 for j in range(M): x*=next(Y[j]); x%=Mod S+=x return S%Mod class Calculator: def __init__(self): self.primitive=self.__primitive_root() self.__build_up() def __primitive_root(self): p=Mod if p==2: return 1 if p==998244353: return 3 if p==10**9+7: return 5 if p==163577857: return 23 if p==167772161: return 3 if p==469762049: return 3 fac=[] q=2 v=p-1 while v>=q*q: e=0 while v%q==0: e+=1 v//=q if e>0: fac.append(q) q+=1 if v>1: fac.append(v) g=2 while g<p: if pow(g,p-1,p)!=1: return None flag=True for q in fac: if pow(g,(p-1)//q,p)==1: flag=False break if flag: return g g+=1 #参考元: https://judge.yosupo.jp/submission/72676 def __build_up(self): rank2=(~(Mod-1) & ((Mod-1)-1)).bit_length() root=[0]*(rank2+1); iroot=[0]*(rank2+1) rate2=[0]*max(0, rank2-1); irate2=[0]*max(0, rank2-1) rate3=[0]*max(0, rank2-2); irate3=[0]*max(0, rank2-2) root[-1]=pow(self.primitive, (Mod-1)>>rank2, Mod) iroot[-1]=pow(root[-1], -1, Mod) for i in range(rank2)[::-1]: root[i]=root[i+1]*root[i+1]%Mod iroot[i]=iroot[i+1]*iroot[i+1]%Mod prod=iprod=1 for i in range(rank2-1): rate2[i]=root[i+2]*prod%Mod irate2[i]=iroot[i+2]*prod%Mod prod*=iroot[i+2]; prod%=Mod iprod*=root[i+2]; iprod%=Mod prod=iprod = 1 for i in range(rank2-2): rate3[i]=root[i + 3]*prod%Mod irate3[i]=iroot[i + 3]*iprod%Mod prod*=iroot[i + 3]; prod%=Mod iprod*=root[i + 3]; iprod%=Mod self.root=root; self.iroot=iroot self.rate2=rate2; self.irate2=irate2 self.rate3=rate3; self.irate3=irate3 def Add(self, A, B): """ 必要ならば末尾に元を追加して, [A[i]+B[i]] を求める. """ if type(A)==int: A=[A] if type(B)==int: B=[B] m=min(len(A), len(B)) C=[(A[i]+B[i])%Mod for i in range(m)] C.extend(A[m:]) C.extend(B[m:]) return C def Sub(self, A, B): """ 必要ならば末尾に元を追加して, [A[i]-B[i]] を求める. """ if type(A)==int: A=[A] if type(B)==int: B=[B] m=min(len(A), len(B)) C=[0]*m C=[(A[i]-B[i])%Mod for i in range(m)] C.extend(A[m:]) C.extend([-b%Mod for b in B[m:]]) return C def Times(self,A, k): """ [k*A[i]] を求める. """ return [k*a%Mod for a in A] #参考元 https://judge.yosupo.jp/submission/72676 def NTT(self, A): """ A に Mod を法とする数論変換を施す ※ Mod はグローバル変数から指定 References: https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp https://judge.yosupo.jp/submission/72676 """ N=len(A) H=(N-1).bit_length() l=0 I=self.root[2] rate2=self.rate2; rate3=self.rate3 while l<H: if H-l==1: p=1<<(H-l-1) rot=1 for s in range(1<<l): offset=s<<(H-l) for i in range(p): x=A[i+offset]; y=A[i+offset+p]*rot%Mod A[i+offset]=(x+y)%Mod A[i+offset+p]=(x-y)%Mod if s+1!=1<<l: rot*=rate2[(~s&-~s).bit_length()-1] rot%=Mod l+=1 else: p=1<<(H-l-2) rot=1 for s in range(1<<l): rot2=rot*rot%Mod rot3=rot2*rot%Mod offset=s<<(H-l) for i in range(p): a0=A[i+offset] a1=A[i+offset+p]*rot a2=A[i+offset+2*p]*rot2 a3=A[i+offset+3*p]*rot3 alpha=(a1-a3)%Mod*I A[i+offset]=(a0+a2+a1+a3)%Mod A[i+offset+p]=(a0+a2-a1-a3)%Mod A[i+offset+2*p]=(a0-a2+alpha)%Mod A[i+offset+3*p]=(a0-a2-alpha)%Mod if s+1!=1<<l: rot*=rate3[(~s&-~s).bit_length()-1] rot%=Mod l+=2 #参考元 https://judge.yosupo.jp/submission/72676 def Inverse_NTT(self, A): """ A を Mod を法とする逆数論変換を施す ※ Mod はグローバル変数から指定 References: https://github.com/atcoder/ac-library/blob/master/atcoder/convolution.hpp https://judge.yosupo.jp/submission/72676 """ N=len(A) H=(N-1).bit_length() l=H J=self.iroot[2] irate2=self.rate2; irate3=self.irate3 while l: if l==1: p=1<<(H-l) irot=1 for s in range(1<<(l-1)): offset=s<<(H-l+1) for i in range(p): x=A[i+offset]; y=A[i+offset+p] A[i+offset]=(x+y)%Mod A[i+offset+p]=(x-y)*irot%Mod if s+1!=1<<(l-1): irot*=irate2[(~s&-~s).bit_length()-1] irot%=Mod l-=1 else: p=1<<(H-l) irot=1 for s in range(1<<(l-2)): irot2=irot*irot%Mod irot3=irot2*irot%Mod offset=s<<(H-l+2) for i in range(p): a0=A[i+offset] a1=A[i+offset+p] a2=A[i+offset+2*p] a3=A[i+offset+3*p] beta=(a2-a3)*J%Mod A[i+offset]=(a0+a1+a2+a3)%Mod A[i+offset+p]=(a0-a1+beta)*irot%Mod A[i+offset+2*p]=(a0+a1-a2-a3)*irot2%Mod A[i+offset+3*p]=(a0-a1-beta)*irot3%Mod if s+1!=1<<(l-2): irot*=irate3[(~s&-~s).bit_length()-1] irot%=Mod l-=2 N_inv=pow(N, -1, Mod) for i in range(N): A[i]=N_inv*A[i]%Mod def non_zero_count(self, A): """ A にある非零の数を求める. """ return len(A)-A.count(0) def is_sparse(self, A, K=None): """ A が疎かどうかを判定する. """ if K==None: K=25 return self.non_zero_count(A)<=K def coefficients_list(self, A): """ A にある非零のリストを求める. output: ( [d[0], ..., d[k-1] ], [f[0], ..., f[k-1] ]) : a[d[j]]=f[j] であることを表している. """ f=[]; d=[] for i in range(len(A)): if A[i]: d.append(i) f.append(A[i]) return d,f def Convolution(self, A, B): """ A, B で Mod を法とする畳み込みを求める. ※ Mod はグローバル変数から指定 """ if not A or not B: return [] N=len(A) M=len(B) L=M+N-1 if min(N,M)<=50: if N<M: N,M=M,N A,B=B,A C=[0]*L for i in range(N): for j in range(M): C[i+j]+=A[i]*B[j] C[i+j]%=Mod return C H=L.bit_length() K=1<<H A=A+[0]*(K-N) B=B+[0]*(K-M) self.NTT(A) self.NTT(B) for i in range(K): A[i]=A[i]*B[i]%Mod self.Inverse_NTT(A) return A[:L] def Autocorrelation(self, A): """ A 自身に対して,Mod を法とする畳み込みを求める. ※ Mod はグローバル変数から指定 """ N=len(A) L=2*N-1 if N<=50: C=[0]*L for i in range(N): for j in range(N): C[i+j]+=A[i]*A[j] C[i+j]%=Mod return C H=L.bit_length() K=1<<H A=A+[0]*(K-N) self.NTT(A) for i in range(K): A[i]=A[i]*A[i]%Mod self.Inverse_NTT(A) return A[:L] def Multiple_Convolution(self, *A): """ A=(A[0], A[1], ..., A[d-1]) で Mod を法とする畳み込みを行う. """ from collections import deque if not A: return [1] Q=deque(list(range(len(A)))) A=list(A) while len(Q)>=2: i=Q.popleft(); j=Q.popleft() A[i]=self.Convolution(A[i], A[j]) A[j]=None Q.append(i) i=Q.popleft() return A[i] def Inverse(self, F, length=None): if length==None: M=len(F) else: M=length if M<=0: return [] if self.is_sparse(F): """ 愚直に漸化式を用いて求める. 計算量: F にある係数が非零の項の個数を K, 求める最大次数を N として, O(NK) 時間 """ d,f=self.coefficients_list(F) G=[0]*M alpha=pow(F[0], -1, Mod) G[0]=alpha for i in range(1, M): for j in range(1, len(d)): if d[j]<=i: G[i]+=f[j]*G[i-d[j]]%Mod else: break G[i]%=Mod G[i]=(-alpha*G[i])%Mod del G[M:] else: """ FFTの理論を応用して求める. 計算量: 求めたい項の個数をNとして, O(N log N) Reference: https://judge.yosupo.jp/submission/42413 """ N=len(F) r=pow(F[0], -1, Mod) m=1 G=[r] while m<M: A=F[:min(N, 2*m)]; A+=[0]*(2*m-len(A)) B=G.copy(); B+=[0]*(2*m-len(B)) Calc.NTT(A); Calc.NTT(B) for i in range(2*m): A[i]=A[i]*B[i]%Mod Calc.Inverse_NTT(A) A=A[m:]+[0]*m Calc.NTT(A) for i in range(2*m): A[i]=-A[i]*B[i]%Mod Calc.Inverse_NTT(A) G.extend(A[:m]) m<<=1 G=G[:M] return G def Floor_Div(self, F, G): assert F[-1] assert G[-1] F_deg=len(F)-1 G_deg=len(G)-1 if F_deg<G_deg: return [] m=F_deg-G_deg+1 return self.Convolution(F[::-1], Calc.Inverse(G[::-1],m))[m-1::-1] def Mod(self, F, G): while F and F[-1]==0: F.pop() while G and G[-1]==0: G.pop() if not F: return [] return Calc.Sub(F, Calc.Convolution(Calc.Floor_Div(F,G),G)) #================================================== class Exp_Poly: def __init__(self, b, poly): self.b = b self.poly = poly def __mul__(self, other): return Exp_Poly((self.b + other.b) % Mod, Calc.Convolution(self.poly, other.poly)) def __repr__(self): return f"({self.b}, {self.poly})" def expection(exp_poly): total = 0 b = exp_poly.b poly = exp_poly.poly if b == 0: return 0 b_inv = pow(b, Mod-2, Mod) b_inv_prod = b_inv for k, c in enumerate(poly): tmp = c * fact[k] % Mod total += tmp * (- b_inv_prod) % Mod; total %= Mod b_inv_prod *= b_inv; b_inv_prod %= Mod return total def popcount(S): pop = 0 while S: pop += 1 x = S & (-S) S ^= x return pop def solve(): from itertools import product N = int(input()) k = [0] * N; a = [0] * N for i in range(N): k[i], a[i] = map(int, input().split()) global Mod, fact, fact_inv, inv, Calc Mod = 998244353 Calc = Calculator() fact, fact_inv = Factor_with_inverse(sum(k)) inv = Modular_Inverse(20) EP = [None] * N for i in range(N): EP[i] = Exp_Poly(pow(a[i], Mod - 2, Mod), [fact_inv[t] * pow(a[i], (Mod - 2) * t, Mod) % Mod for t in range(k[i])]) prod = [None for _ in range(1 << N)] prod[0] = Exp_Poly(0, [1]) D = [0] * (1 << N); D[0] = expection(prod[0]) for S in range(1, 1 << N): x = S & (-S) i = x.bit_length() - 1 prod[S] = prod[S ^ x] * EP[i] D[S] = expection(prod[S]) E_pre = [0] * (N + 1) for V in product([0, 1, 2], repeat = N): S = T = U = 0 for i in range(N): if V[i] == 0: S |= 1 << i elif V[i] == 1: T |= 1 << i else: U |= 1 << i deg = popcount(S | T) E_pre[deg] += pow(-1, popcount(T), Mod) * D[T | U] E_pre[deg] %= Mod E = [0] * (N + 1) E[N] = E_pre[N] for d in range(N-1, -1, -1): E[d] = (E[d + 1] + E_pre[d]) % Mod return E[1:] #================================================== print(*solve())