Submit Info #37576

Problem Lang User Status Time Memory
Polynomial Taylor Shift pypy3 Kazu1998k AC 522 ms 142.04 MiB

ケース詳細
Name Status Time Memory
example_00 AC 52 ms 29.54 MiB
example_01 AC 53 ms 29.53 MiB
fft_killer_00 AC 522 ms 140.08 MiB
fft_killer_01 AC 521 ms 140.07 MiB
max_random_00 AC 520 ms 140.07 MiB
max_random_01 AC 522 ms 140.04 MiB
medium_00 AC 78 ms 31.00 MiB
medium_01 AC 81 ms 31.30 MiB
medium_02 AC 80 ms 31.38 MiB
medium_all_zero_00 AC 77 ms 30.72 MiB
medium_c_zero_00 AC 77 ms 31.00 MiB
random_00 AC 498 ms 125.10 MiB
random_01 AC 507 ms 142.04 MiB
random_02 AC 125 ms 43.03 MiB
small_00 AC 51 ms 29.61 MiB
small_01 AC 51 ms 29.58 MiB
small_02 AC 52 ms 29.52 MiB
small_03 AC 52 ms 29.56 MiB
small_04 AC 52 ms 29.62 MiB
small_05 AC 52 ms 29.62 MiB
small_06 AC 52 ms 29.56 MiB
small_07 AC 52 ms 29.56 MiB
small_08 AC 52 ms 29.56 MiB
small_09 AC 52 ms 29.56 MiB
small_10 AC 53 ms 29.50 MiB
small_11 AC 53 ms 29.54 MiB
small_12 AC 53 ms 29.57 MiB
small_13 AC 53 ms 29.58 MiB
small_14 AC 54 ms 29.64 MiB
small_15 AC 54 ms 29.61 MiB

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 __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] def Taylor_Shift(P,a): """与えられた多項式 P に対して, P(X+a) を求める. P: Polynominal a: int """ N=len(P.Poly)-1 fact=[0]*(N+1) fact[0]=1 for i in range(1,N+1): fact[i]=(fact[i-1]*i)%Mod fact_inv=[0]*(N+1) fact_inv[-1]=pow(fact[-1],Mod-2,Mod) for i in range(N-1,-1,-1): fact_inv[i]=(fact_inv[i+1]*(i+1))%Mod F=P.Poly.copy() for i in range(N+1): F[i]=(F[i]*fact[i])%Mod G=[0]*(N+1) c=1 for i in range(N+1): G[i]=(c*fact_inv[i])%Mod c=(c*a)%Mod G.reverse() H=Convolution_Mod(F,G)[N:] for i in range(len(H)): H[i]=(H[i]*fact_inv[i])%Mod return Modulo_Polynominal(H,P.Max_Degree,P.Char) #================================================ import sys input=sys.stdin.readline write=sys.stdout.write Mod=998244353 N,c=map(int,input().split()) A=list(map(int,input().split())) A=Modulo_Polynominal(A,N) B=Taylor_Shift(A,c) B.resize(N) write(" ".join(map(str,B.Poly)))