結果
問題 | No.931 Multiplicative Convolution |
ユーザー | 👑 Kazun |
提出日時 | 2021-05-19 15:00:00 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 13,607 bytes |
コンパイル時間 | 567 ms |
コンパイル使用メモリ | 81,888 KB |
実行使用メモリ | 113,284 KB |
最終ジャッジ日時 | 2024-10-09 18:59:10 |
合計ジャッジ時間 | 4,443 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 41 ms
55,436 KB |
testcase_01 | AC | 42 ms
56,496 KB |
testcase_02 | AC | 42 ms
55,832 KB |
testcase_03 | AC | 41 ms
55,788 KB |
testcase_04 | WA | - |
testcase_05 | WA | - |
testcase_06 | WA | - |
testcase_07 | WA | - |
testcase_08 | WA | - |
testcase_09 | AC | 246 ms
113,284 KB |
testcase_10 | AC | 249 ms
106,100 KB |
testcase_11 | AC | 237 ms
109,928 KB |
testcase_12 | WA | - |
testcase_13 | WA | - |
testcase_14 | WA | - |
testcase_15 | WA | - |
testcase_16 | WA | - |
ソースコード
class Modulo_Polynominal(): def __init__(self,Poly,Max_Degree=2*10**5,Char="X"): from itertools import zip_longest """多項式の定義 P:係数のリスト C:文字 Max_Degree ※Mod:法はグローバル変数から指定 """ self.Poly=[p%Mod for p in Poly[:Max_Degree]] self.Char=Char self.Max_Degree=Max_Degree self.minus=10**7 def __str__(self): if bool(self): M=[(k,a) for k,a in enumerate(self.Poly) if a] for i in range(len(M)): k,a=M[i] if Mod-a<=self.minus: M[i]=(k,a-Mod) A=["{} {} ^ {} ".format(a,self.Char,k) for k,a in M] S=" "+" + ".join(A) S=S.replace(" + -"," - ") S=S.replace(" {} ^ 0 ".format(self.Char),"") S=S.replace(" {} ^ 1 ".format(self.Char)," "+self.Char+" ") S=S.replace(" 1 {} ".format(self.Char),self.Char+" ") S=S.replace(" -1 {} ".format(self.Char),"-"+self.Char+" ") S=S.replace(" ","") else: S="0" S+=" (mod (Z/ {0} Z)[{1}]/ ({1}^{2}))".format(Mod,self.Char,self.Max_Degree) return S.strip() def __repr__(self): return self.__str__() #= def __eq__(self,other): if self.Max_Degree!=other.Max_Degree: return False from itertools import zip_longest return all([a==b for a,b in zip_longest(self.Poly,other.Poly,fillvalue=0)]) #+,- def __pos__(self): return self def __neg__(self): return self.scale(-1) #Boole def __bool__(self): return any(self.Poly) #簡略化 def reduce(self): P_deg=self.degree() if not(P_deg>=0): self.Poly=[0] self.censor(self.Max_Degree) return for i in range(self.degree(),-1,-1): if self.Poly[i]: self.Poly=self.Poly[:i+1] self.censor(self.Max_Degree) return self.Poly=[] return #シフト def __lshift__(self,other): if other<0: return self>>(-other) if other>self.Max_Degree: return Modulo_Polynominal([0],self.Max_Degree,self.Char) G=[0]*other+self.Poly return Modulo_Polynominal(G,self.Max_Degree,self.Char) def __rshift__(self,other): if other<0: return self<<(-other) return Modulo_Polynominal(self.Poly[other:],self.Max_Degree,self.Char) #次数 def degree(self): d=len(self.Poly)-1 for y in self.Poly[::-1]: if y: return d d-=1 return -float("inf") #加法 def __add__(self,other): P=self Q=other if Q.__class__==Modulo_Polynominal: from itertools import zip_longest N=min(P.Max_Degree,Q.Max_Degree) R=[(a+b)%Mod for (a,b) in zip_longest(P.Poly,Q.Poly,fillvalue=0)] return Modulo_Polynominal(R,N,P.Char) else: P_deg=P.degree() if P_deg<0:P_deg=0 R=[0]*(P_deg+1) R=[p for p in P.Poly] R[0]=(R[0]+Q)%Mod R=Modulo_Polynominal(R,P.Max_Degree,P.Char) R.reduce() return R def __radd__(self,other): return self+other #減法 def __sub__(self,other): return self+(-other) def __rsub__(self,other): return (-self)+other #乗法 def __mul__(self,other): P=self Q=other if Q.__class__==Modulo_Polynominal: a=b=0 for x in P.Poly: if x: a+=1 for y in Q.Poly: if y: b+=1 if a>b: P,Q=Q,P P.reduce();Q.reduce() U,V=P.Poly,Q.Poly M=min(P.Max_Degree,Q.Max_Degree) if a<2*P.Max_Degree.bit_length(): B=[0]*(len(U)+len(V)-1) for i in range(len(U)): if U[i]: for j in range(len(V)): B[i+j]+=U[i]*V[j] if B[i+j]>Mod: B[i+j]-=Mod else: B=Convolution_Mod(U,V)[:M] B=Modulo_Polynominal(B,M,self.Char) B.reduce() return B else: return self.scale(other) def __rmul__(self,other): return self.scale(other) #除法 def __floordiv__(self,other): if not other: raise ZeroDivisionError if isinstance(other,int): return self/other F,G=self,other N=min(F.Max_Degree,G.Max_Degree) F_deg=F.degree() G_deg=G.degree() if F_deg<G_deg: A=Modulo_Polynominal([0],N,self.Char) A.reduce() return A G.reduce() F_inv=Modulo_Polynominal(F.Poly[::-1],F.Max_Degree,F.Char) G_inv=Modulo_Polynominal(G.Poly[::-1],F.Max_Degree,F.Char) H=F_inv/G_inv H.censor(F_deg-G_deg+1) return Modulo_Polynominal(H.Poly[::-1],N,self.Char) def __rfloordiv__(self,other): if not self: raise ZeroDivisionError if isinstance(other,int): return Modulo_Polynominal([0],self.Max_Degree,self.Char) #剰余 def __mod__(self,other): if not other: return ZeroDivisionError return self-(self//other)*other def __rmod__(self,other): if not self: raise ZeroDivisionError return other-(other//self)*self def __divmod__(self,other): p=self//other return (p,self-other*p) #累乗 def __pow__(self,other): if other.__class__==int: n=other m=abs(n) Q=self A=Modulo_Polynominal([1],self.Max_Degree,self.Char) while m>0: if m&1: A*=Q m>>=1 Q*=Q if n>=0: return A else: return A.__inv__() else: P=Log(self) return Exp(P*other) #逆元 def __inv__(self,deg=None): assert self.Poly[0],"定数項が0" P=self if len(P.Poly)<=P.Max_Degree.bit_length(): """ 愚直に漸化式を用いて求める. 計算量:Pの次数をK, 求めたい項の個数をNとして, O(NK) """ F=P.Poly c=F[0] c_inv=pow(c,Mod-2,Mod) N=len(P.Poly) R=[-c_inv*a%Mod for a in F[1:]][::-1] G=[0]*P.Max_Degree G[0]=1 Q=[0]*(N-2)+[1] for k in range(1,P.Max_Degree): a=0 for x,y in zip(Q,R): a+=x*y a%=Mod G[k]=a Q.append(a) Q=Q[1:] G=[c_inv*g%Mod for g in G] return Modulo_Polynominal(G,P.Max_Degree,P.Char) else: """ FFTの理論を応用して求める. 計算量:求めたい項の個数をNとして, O(N log N) """ if deg==None: deg=P.Max_Degree else: deg=min(deg,P.Max_Degree) F=P.Poly N=len(F) r=pow(F[0],Mod-2,Mod) m=1 G=[r] while m<deg: T=F[:m<<1] H=Convolution_Mod(T,G)[m:m<<1] L=Convolution_Mod(H,G)[:m] for a in L: G.append(Mod-a) m<<=1 return Modulo_Polynominal(G[:deg],P.Max_Degree,P.Char) #除法 def __truediv__(self,other): if isinstance(other,Modulo_Polynominal): return self*other.__inv__() else: return pow(other,Mod-2,Mod)*self def __rtruediv__(self,other): return other*self.__inv__() #スカラー倍 def scale(self,s): P=self s%=Mod A=[(s*p)%Mod for p in P.Poly] A=Modulo_Polynominal(A,P.Max_Degree,P.Char) A.reduce() return A #係数 def coefficient(self,n): try: if n<0: raise IndexError return self.Poly[n] except IndexError: return 0 except TypeError: return 0 #最高次の係数 def leading_coefficient(self): for x in self.Poly[::-1]: if x: return x return 0 def censor(self,n,Return=False): """ n次以上の係数をカット """ if Return: return Modulo_Polynominal(self.Poly[:n],self.Max_Degree,self.Char) else: self.Poly=self.Poly[:n] def resize(self,n,Return=False): P=self if Return: if len(P.Poly)>n: E=P.Poly[:n] else: E=P.Poly+[0]*(n-P.Poly) return Modulo_Polynominal(E,P.Max_Degree,P.Char) else: if len(P.Poly)>n: del P.Poly[n:] else: P.Poly+=[0]*(n-len(P.Poly)) #================================================= def Primitive_Root(p): """Z/pZ上の原始根を見つける p:素数 """ 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://atcoder.jp/contests/practice2/submissions/16789717 def NTT(A): """AをMod を法とする数論変換を施す ※Modはグローバル変数から指定 """ primitive=Primitive_Root(Mod) N=len(A) H=(N-1).bit_length() if Mod==998_244_353: m=998_244_352 u=119 e=23 S=[1,998244352,911660635,372528824,929031873, 452798380,922799308,781712469,476477967,166035806, 258648936,584193783,63912897,350007156,666702199, 968855178,629671588,24514907,996173970,363395222, 565042129,733596141,267099868,15311432] else: m=Mod-1 e=((m&-m)-1).bit_length() u=m>>e S=[pow(primitive,(Mod-1)>>i,Mod) for i in range(e+1)] for l in range(H, 0, -1): d = 1 << l - 1 U = [1]*(d+1) u = 1 for i in range(d): u=u*S[l]%Mod U[i+1]=u for i in range(1 <<H - l): s=2*i*d for j in range(d): A[s],A[s+d]=(A[s]+A[s+d])%Mod, U[j]*(A[s]-A[s+d])%Mod s+=1 #参考元 https://atcoder.jp/contests/practice2/submissions/16789717 def Inverse_NTT(A): """AをMod を法とする逆数論変換を施す ※Modはグローバル変数から指定 """ primitive=Primitive_Root(Mod) N=len(A) H=(N-1).bit_length() if Mod==998244353: m=998_244_352 e=23 u=119 S=[1,998244352,86583718,509520358,337190230, 87557064,609441965,135236158,304459705,685443576, 381598368,335559352,129292727,358024708,814576206, 708402881,283043518,3707709,121392023,704923114,950391366, 428961804,382752275,469870224] else: m=Mod-1 e=(m&-m).bit_length()-1 u=m>>e inv_primitive=pow(primitive,Mod-2,Mod) S=[pow(inv_primitive,(Mod-1)>>i,Mod) for i in range(e+1)] for l in range(1, H + 1): d = 1 << l - 1 for i in range(1 << H - l): u = 1 for j in range(2*i*d, (2*i+1)*d): A[j+d] *= u A[j], A[j+d] = (A[j] + A[j+d]) % Mod, (A[j] - A[j+d]) % Mod u = u * S[l] % Mod N_inv=pow(N,Mod-2,Mod) for i in range(N): A[i]=A[i]*N_inv%Mod #参考元 https://atcoder.jp/contests/practice2/submissions/16789717 def Convolution_Mod(A,B): """A,BをMod を法とする畳み込みを求める. ※Modはグローバル変数から指定 """ if not A or not B: return [] N=len(A) M=len(B) L=N+M-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) NTT(A) NTT(B) for i in range(K): A[i]=A[i]*B[i]%Mod Inverse_NTT(A) return A[:L] #================================================== P=int(input()) A=[-1]+list(map(int,input().split())) B=[-1]+list(map(int,input().split())) Mod=998244353 g=Primitive_Root(P) U=[0]*(P-1); V=[0]*(P-1) x=1 for i in range(P-1): U[i]=A[x] V[i]=B[x] x*=g x%=P W=Convolution_Mod(U,V) for i in range(P-1,len(W)): W[i%(P-1)]+=W[i] C=[0]*P x=1 for i in range(P-1): C[x]=W[i] x*=g x%=P print(*C[1:])