class Modulo_Polynominal(): def __init__(self,Poly,Max_Degree=2*10**5,Char="x"): """多項式の定義 P:係数のリスト C:文字 Max_Degree ※Mod:法はグローバル変数から指定 """ self.Poly=[p%Mod for p in Poly] self.Char=Char self.Max_Degree=Max_Degree def __str__(self): S="" flag=False for k in range(len(self.Poly)): if self.Poly[k]: if flag: if k==1: S+="{:+}{}".format(self.Poly[1],self.Char) else: S+="{:+}{}^{}".format(self.Poly[k],self.Char,k) else: flag=True if k==0: S=str(self.Poly[0]) elif k==1: S=str(self.Poly[1])+self.Char else: S=str(self.Poly[k])+"{}^{}".format(self.Char,k) if S: return S else: return "0" #+,- def __pos__(self): return self def __neg__(self): return self.scale(-1) #Boole def __bool__(self): for a in self.Poly: if a: return True return False #簡略化 def reduce(self): P_deg=self.degree() if not(P_deg>=0): T=Modulo_Polynominal([0],self.Max_Degree,self.Char) T.censor(self.Max_Degree) return T for i in range(self.degree(),-1,-1): if self.Poly[i]: T=Modulo_Polynominal(self.Poly[:i+1],self.Max_Degree,self.Char) T.censor(self.Max_Degree) return T #次数 def degree(self): x=-float("inf") k=0 for y in self.Poly: if y!=0: x=k k+=1 return x #加法 def __add__(self,other): P=self Q=other if Q.__class__==Modulo_Polynominal: P_deg=max(P.degree(),0) Q_deg=max(Q.degree(),0) N=min(P_deg,Q_deg) R=[(P.Poly[k]+Q.Poly[k])%Mod for k in range(N+1)] if P_deg>=Q_deg: R+=self.Poly[Q_deg+1:] else: R+=other.Poly[P_deg+1:] return Modulo_Polynominal(R,P.Max_Degree,P.Char).reduce() else: P_deg=P.degree() R=[0]*(P_deg+1) R=[p for p in P.Poly] R[0]=(R[0]+Q)%Mod return Modulo_Polynominal(R,P.Max_Degree,P.Char).reduce() 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: M=min(P.Max_Degree,Q.Max_Degree) B=Convolution_Mod(self.Poly,other.Poly)[:M] return Modulo_Polynominal(B,M,self.Char).reduce() else: return self.scale(other) def __rmul__(self,other): return self.scale(other) #除法 def __floordiv__(self,other): if not other: raise ZeroDivisionError pass #剰余 def __mod__(self,other): return self-(self//other)*other #累乗 def __pow__(self,n): 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__() #逆元 def __inv__(self,deg=None): assert self.Poly[0],"定数項が0" P=self 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 T=[r] while m=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>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 <>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(i * 2 * d, (i * 2 + 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はグローバル変数から指定 """ L=len(A)+len(B)-1 H=L.bit_length() N=1<