結果
問題 | No.1549 [Cherry 2nd Tune] BANning Tuple |
ユーザー |
👑 ![]() |
提出日時 | 2021-03-29 04:36:21 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 2,963 ms / 4,000 ms |
コード長 | 17,606 bytes |
コンパイル時間 | 325 ms |
コンパイル使用メモリ | 82,048 KB |
実行使用メモリ | 173,056 KB |
最終ジャッジ日時 | 2024-12-14 19:28:43 |
合計ジャッジ時間 | 48,844 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 20 |
ソースコード
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=Charself.Max_Degree=Max_Degreeself.minus=10**7def __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 Falsefrom itertools import zip_longestreturn all([a==b for a,b in zip_longest(self.Poly,other.Poly,fillvalue=0)])#+,-def __pos__(self):return selfdef __neg__(self):return self.scale(-1)#Booledef __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)returnfor i in range(self.degree(),-1,-1):if self.Poly[i]:self.Poly=self.Poly[:i+1]self.censor(self.Max_Degree)returnself.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.Polyreturn 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)-1for y in self.Poly[::-1]:if y:return dd-=1return -float("inf")#加法def __add__(self,other):P=selfQ=otherif Q.__class__==Modulo_Polynominal:from itertools import zip_longestN=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=0R=[0]*(P_deg+1)R=[p for p in P.Poly]R[0]=(R[0]+Q)%ModR=Modulo_Polynominal(R,P.Max_Degree,P.Char)R.reduce()return Rdef __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=selfQ=otherif Q.__class__==Modulo_Polynominal:a=b=0for x in P.Poly:if x:a+=1for y in Q.Poly:if y:b+=1if a>b:P,Q=Q,PP.reduce();Q.reduce()U,V=P.Poly,Q.PolyM=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]-=Modelse:B=Convolution_Mod(U,V)[:M]B=Modulo_Polynominal(B,M,self.Char)B.reduce()return Belse:return self.scale(other)def __rmul__(self,other):return self.scale(other)#除法def __floordiv__(self,other):if not other:raise ZeroDivisionErrorif isinstance(other,int):return self/otherF,G=self,otherN=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 AG.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_invH.censor(F_deg-G_deg+1)return Modulo_Polynominal(H.Poly[::-1],N,self.Char)def __rfloordiv__(self,other):if not self:raise ZeroDivisionErrorif isinstance(other,int):return Modulo_Polynominal([0],self.Max_Degree,self.Char)#剰余def __mod__(self,other):if not other:return ZeroDivisionErrorreturn self-(self//other)*otherdef __rmod__(self,other):if not self:raise ZeroDivisionErrorreturn other-(other//self)*selfdef __divmod__(self,other):p=self//otherreturn (p,self-other*p)#累乗def __pow__(self,other):if other.__class__==int:n=otherm=abs(n)Q=selfA=Modulo_Polynominal([1],self.Max_Degree,self.Char)while m>0:if m&1:A*=Qm>>=1Q*=Qif n>=0:return Aelse:return A.__inv__()else:P=Log(self)return Exp(P*other)#逆元def __inv__(self,deg=None):assert self.Poly[0],"定数項が0"P=selfif len(P.Poly)<=P.Max_Degree.bit_length():"""愚直に漸化式を用いて求める.計算量:Pの次数をK, 求めたい項の個数をNとして, O(NK)"""F=P.Polyc=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_DegreeG[0]=1Q=[0]*(N-2)+[1]for k in range(1,P.Max_Degree):a=0for x,y in zip(Q,R):a+=x*ya%=ModG[k]=aQ.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_Degreeelse:deg=min(deg,P.Max_Degree)F=P.PolyN=len(F)r=pow(F[0],Mod-2,Mod)m=1G=[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<<=1return 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)*selfdef __rtruediv__(self,other):return other*self.__inv__()#スカラー倍def scale(self,s):P=selfs%=ModA=[(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 IndexErrorreturn self.Poly[n]except IndexError:return 0except TypeError:return 0#最高次の係数def leading_coefficient(self):for x in self.Poly[::-1]:if x:return xreturn 0def 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=selfif 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 1if p==998244353:return 3if p==10**9+7:return 5if p==163577857:return 23if p==167772161:return 3if p==469762049:return 3fac=[]q=2v=p-1while v>=q*q:e=0while v%q==0:e+=1v//=qif e>0:fac.append(q)q+=1if v>1:fac.append(v)g=2while g<p:if pow(g,p-1,p)!=1:return Noneflag=Truefor q in fac:if pow(g,(p-1)//q,p)==1:flag=Falsebreakif flag:return gg+=1#参考元 https://atcoder.jp/contests/practice2/submissions/16789717def 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_352u=119e=23S=[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-1e=((m&-m)-1).bit_length()u=m>>eS=[pow(primitive,(Mod-1)>>i,Mod) for i in range(e+1)]for l in range(H, 0, -1):d = 1 << l - 1U = [1]*(d+1)u = 1for i in range(d):u=u*S[l]%ModU[i+1]=ufor i in range(1 <<H - l):s=2*i*dfor j in range(d):A[s],A[s+d]=(A[s]+A[s+d])%Mod, U[j]*(A[s]-A[s+d])%Mods+=1#参考元 https://atcoder.jp/contests/practice2/submissions/16789717def Inverse_NTT(A):"""AをMod を法とする逆数論変換を施す※Modはグローバル変数から指定"""primitive=Primitive_Root(Mod)N=len(A)H=(N-1).bit_length()if Mod==998244353:m=998_244_352e=23u=119S=[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-1e=(m&-m).bit_length()-1u=m>>einv_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 - 1for i in range(1 << H - l):u = 1for j in range(2*i*d, (2*i+1)*d):A[j+d] *= uA[j], A[j+d] = (A[j] + A[j+d]) % Mod, (A[j] - A[j+d]) % Modu = u * S[l] % ModN_inv=pow(N,Mod-2,Mod)for i in range(N):A[i]=A[i]*N_inv%Mod#参考元 https://atcoder.jp/contests/practice2/submissions/16789717def Convolution_Mod(A,B):"""A,BをMod を法とする畳み込みを求める.※Modはグローバル変数から指定"""if not A or not B:return []N=len(A)M=len(B)L=N+M-1if min(N,M)<=50:if N<M:N,M=M,NA,B=B,AC=[0]*Lfor i in range(N):for j in range(M):C[i+j]+=A[i]*B[j]C[i+j]%=Modreturn CH=L.bit_length()K=1<<HA=A+[0]*(K-N)B=B+[0]*(K-M)NTT(A)NTT(B)for i in range(K):A[i]=A[i]*B[i]%ModInverse_NTT(A)return A[:L]def Autocorrelation_Mod(A):"""A自身に対して,Mod を法とする畳み込みを求める.※Modはグローバル変数から指定"""N=len(A)L=2*N-1if N<=50:C=[0]*Lfor i in range(N):for j in range(N):C[i+j]+=A[i]*A[j]C[i+j]%=Modreturn CH=L.bit_length()K=1<<HA=A+[0]*(K-N)NTT(A)for i in range(K):A[i]=A[i]*A[i]%ModInverse_NTT(A)return A[:L]#以下 参考元https://judge.yosupo.jp/submission/28304def inverse(F):G=[pow(F[0],Mod-2,Mod)]N=len(F)d=1while d<N:d<<=1H=[-v for v in Convolution_Mod(F[:d],G)[:d]]H[0]+=2G=Convolution_Mod(G,H)[:d]return G[:N]def Differentiate(P):F=P.PolyG=[(k*a)%Mod for k,a in enumerate(F[1:],1)]+[0]return Modulo_Polynominal(G,P.Max_Degree,P.Char)def Integrate(P):F=P.PolyN=len(F)Inv=[0]*(N+1)if N:Inv[1]=1for i in range(2,N+1):q,r=divmod(Mod,i)Inv[i]=(-q*Inv[r])%ModG=[0]+[(Inv[k]*a)%Mod for k,a in enumerate(F,1)]return Modulo_Polynominal(G,P.Max_Degree,P.Char)def Add(a, b):return [(va + vb) % Mod for va, vb in zip(a, b)]def Sub(a, b):return [(va - vb) % Mod for va, vb in zip(a, b)]def Times(a, k):return [v * k % Mod for v in a]def Mul(a,b):return Convolution_Mod(a,b)"""累乗,指数,対数"""def Log(P):assert P.Poly[0]==1,"定数項が1ではない"return Integrate(Differentiate(P)/P)def Exp(P):#参考元1:https://arxiv.org/pdf/1301.5804.pdf#参考元2:https://opt-cp.com/fps-fast-algorithms/from itertools import zip_longestN=P.Max_DegreeInv=[0]*(2*N+1)Inv[1]=1for i in range(2,2*N+1):q,r=divmod(Mod,i)Inv[i]=(-q*Inv[r])%ModH=P.Polyassert (not H) or H[0]==0,"定数項が0でない"H+=[0]*(N-len(H))dH=[(k*a)%Mod for k,a in enumerate(H[1:],1)]F,G,m=[1],[1],1while m<=N:#2.a'if m>1:E=Convolution_Mod(F,Autocorrelation_Mod(G)[:m])[:m]G=[(2*a-b)%Mod for a,b in zip_longest(G,E,fillvalue=0)]#2.b', 2.c'C=Convolution_Mod(F,dH[:m-1])R=[0]*mfor i,a in enumerate(C):R[i%m]+=aR=[a%Mod for a in R]#2.d'dF=[(k*a)%Mod for k,a in enumerate(F[1:],1)]D=[0]+[(a-b)%Mod for a,b in zip_longest(dF,R,fillvalue=0)]S=[0]*mfor i,a in enumerate(D):S[i%m]+=aS=[a%Mod for a in S]#2.e'T=Convolution_Mod(G,S)[:m]#2.f'E=[0]*(m-1)+TE=[0]+[(Inv[k]*a)%Mod for k,a in enumerate(E,1)]U=[(a-b)%Mod for a,b in zip_longest(H[:2*m],E,fillvalue=0)][m:]#2.g'V=Convolution_Mod(F,U)[:m]#2.h'F+=V#2.i'm<<=1return Modulo_Polynominal(F[:N],P.Max_Degree,P.Char)def Power(P,k):assert k>=0N=P.Max_DegreeF=P.PolyF+=[0]*(N-len(F))for (d,p) in enumerate(F):if p:breakelse:return Modulo_Polynominal([0],P.Max_Degree,P.Char)if d*k>P.Max_Degree:return Modulo_Polynominal([0],P.Max_Degree,P.Char)p_inv=pow(p,Mod-2,Mod)Q=Modulo_Polynominal([(p_inv*a)%Mod for a in F[d:]],P.Max_Degree,P.Char)G=Exp(k*Log(Q)).Polypk=pow(p,k,Mod)G=[0]*(d*k)+[(pk*a)%Mod for a in G]return Modulo_Polynominal(G,P.Max_Degree,P.Char)#================================================def floating_degree(P):T=P.Polyfor i in range(len(T)):if T[i]:return i#================================================import sysfrom collections import defaultdictinput=sys.stdin.readlinewrite=sys.stdout.writeN,Q=map(int,input().split())M=5000Mod=998244353Poly=defaultdict(lambda :Modulo_Polynominal([1]*(M+1),M+1))X=Modulo_Polynominal([0,1],M+1)V=Power(1/(1-X),N+1)Z=[0]*Qoffset=0for i in range(Q):K,A,B,S,T=map(int,input().split())P=Poly[K]#P=0 のときを例外処理if not P:Z[i]=0continued=floating_degree(P)V/=(P>>d)V<<=dfor j in range(A,B+1):P.Poly[j]=0V*=Pif S==0:Z[i]=V.coefficient(T)else:Z[i]=V.coefficient(T)-V.coefficient(S-1)Z[i]%=Modwrite("\n".join(map(str,Z)))