結果
問題 | No.3046 yukicoderの過去問 |
ユーザー | 👑 Kazun |
提出日時 | 2020-12-04 18:21:25 |
言語 | PyPy3 (7.3.15) |
結果 |
WA
|
実行時間 | - |
コード長 | 18,101 bytes |
コンパイル時間 | 204 ms |
コンパイル使用メモリ | 81,920 KB |
実行使用メモリ | 167,156 KB |
最終ジャッジ日時 | 2024-09-15 05:08:13 |
合計ジャッジ時間 | 13,481 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 64 ms
60,032 KB |
testcase_01 | AC | 61 ms
60,032 KB |
testcase_02 | AC | 62 ms
60,416 KB |
testcase_03 | WA | - |
testcase_04 | AC | 82 ms
71,808 KB |
testcase_05 | TLE | - |
testcase_06 | TLE | - |
testcase_07 | TLE | - |
testcase_08 | TLE | - |
ソースコード
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 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: 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() 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<deg: T+=[0]*m m<<=1 E=Convolution_Mod(F[:m],Autocorrelation_Mod(T)[:m]) T=[(2*T[i]-E[i])%Mod for i in range(m)] del T[deg:] return Modulo_Polynominal(T,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] return Modulo_Polynominal(A,P.Max_Degree,P.Char).reduce() #係数 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(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はグローバル変数から指定 """ 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) del A[L:] return A def Autocorrelation_Mod(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) NTT(A) for i in range(K): A[i]=A[i]*A[i]%Mod Inverse_NTT(A) return A[:L] #以下 参考元https://judge.yosupo.jp/submission/28304 def inverse(F): G=[pow(F[0],Mod-2,Mod)] N=len(F) d=1 while d<N: d<<=1 H=[-v for v in Convolution_Mod(F[:d],G)[:d]] H[0]+=2 G=Convolution_Mod(G,H)[:d] return G[:N] def Differentiate(P): F=P.Poly G=[(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.Poly G=[0]+[(pow(k,Mod-2,Mod)*a)%Mod for k,a in enumerate(F,1)] return Modulo_Polynominal(G,P.Max_Degree,P.Char) def Log(P): return Integrate(Differentiate(P)/P) 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 Exp(P): N=P.Max_Degree F=P.Poly F+=[0]*(N-len(F)) G, G_inv = [1], [1] dF=[(k*a)%Mod for k,a in enumerate(F[1:],1)]+[0]*(N-len(F)) d=1 while d<N: H=Convolution_Mod(G,Autocorrelation_Mod(G_inv)[:d]) G_inv=[(2*a-b)%Mod for a,b in zip(G_inv,H)] G+=[0]*d G_inv+=[0]*d d<<= 1 dG=[(k*a)%Mod for k,a in enumerate(G[1:],1)]+[0] W=[(a+b)%Mod for a,b in zip(dF[:d], Convolution_Mod(G_inv,Sub(dG,Convolution_Mod(G,dF[:d])[:d])))] iW=[0]+[(pow(k,Mod-2,Mod)*a)%Mod for k,a in enumerate(W,1)] G=[(a+b)%Mod for (a,b) in zip(G, Convolution_Mod(G,Sub(F[:d],iW))[:d])] return Modulo_Polynominal(G[:N],P.Max_Degree,P.Char) def Power(P,k): N=P.Max_Degree F=P.Poly F+=[0]*(N-len(F)) for (d,p) in enumerate(F): if p: break else: 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)).Poly pk=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 Legendre(X): """ルジャンドル記号(a/p)を返す. ※法が素数のときのみ成立する. """ if X==0: return 0 elif pow(X,(Mod-1)//2,Mod)==1: return 1 else: return -1 #根号 def Tonelli_Shanks(X): """X=a (mod p)のとき,r*r=a (mod p)を満たすrを返す. ※法pが素数のときのみ有効 ※存在しないときはNoneが返り値 """ X%=Mod if Legendre(X)==-1: return None from random import randint as ri if X==0: return X elif Mod==2: return X elif Mod%4==3: return pow(X,(Mod+1)//4,Mod) u=2 s=1 while (Mod-1)%(2*u)==0: u*=2 s+=1 q=(Mod-1)//u z=0 while pow(z,(Mod-1)//2,Mod)!=Mod-1: z=ri(1,Mod-1) m,c,t,r=s,pow(z,q,Mod),pow(X,q,Mod),pow(X,(q+1)//2,Mod) while m>1: if pow(t,2**(m-2),Mod)==1: c=(c*c)%Mod m=m-1 else: c,t,r,m=(c*c)%Mod,(c*c*t)%Mod,(c*r)%Mod,m-1 return r #多項式の根号 def __sqrt(F,N): F+=[0]*(N-len(F)) s=Tonelli_Shanks(F[0]) if s==None:return None m=1 G=[min(s,Mod-s)] two_inv=pow(2,Mod-2,Mod) while m<N: G+=[0]*m m<<=1 H=Convolution_Mod(F[:m],inverse(G)) G=[two_inv*(a+b)%Mod for a,b in zip(G,H)] return G[:N] def Sqrt(P): N=P.Max_Degree F=P.Poly F+=[0]*(N-len(F)) for d,p in enumerate(F): if p:break else: return Modulo_Polynominal([0],P.Max_Degree,P.Char) if d&1:return E=__sqrt(F[d:],N-d//2) if E==None:return if d>0: E=[0]*(d//2)+E return Modulo_Polynominal(E,P.Max_Degree,P.Char) #Bernoulli def Bernoulli(N): """ ベルヌーイ数 B_0,B_1,...,B_Nの(mod Mod)での値を求める. """ if N==0: return [1] X=Modulo_Polynominal([0,1],N+2) P=Exp(X) del P.Poly[0] F=(1/P).Poly fact=1 for i in range(N+1): F[i]=(F[i]*fact)%Mod fact=(fact*(i+1))%Mod del F[-1] return F def Subset_Sum(X,K): """Xの要素のうち,任意個を用いて, 和がk=0,1,...,Kになる組み合わせの総数をModで割った余りを求める. X:リスト (X[0]=0) K:非負整数 """ A=[0]*(K+1) for x in X: if x<=K: A[x]+=1 Inv=[0]*(K+1) Inv[1]=1 for i in range(2,K+1): Inv[i]=(-(Mod//i)*Inv[Mod%i])%Mod F=[0]*(K+1) for i in range(1,K+1): j=i k=1 c=1 while j<=K: F[j]=(F[j]+c*Inv[k]*A[i])%Mod c*=-1 j+=i k+=1 P=Modulo_Polynominal(F,K+1) return Exp(P).Poly class Modulo_Error(Exception): pass class Modulo(): def __init__(self,a,n): self.a=a%n self.n=n def __str__(self): return "{} (mod {})".format(self.a,self.n) #+,- def __pos__(self): return self def __neg__(self): return Modulo(-self.a,self.n) #等号,不等号 def __eq__(self,other): if isinstance(other,Modulo): return (self.a==other.a) and (self.n==other.n) elif isinstance(other,int): return (self-other).a==0 def __neq__(self,other): return not(self==other) #加法 def __add__(self,other): if isinstance(other,Modulo): if self.n!=other.n: raise Modulo_Error("異なる法同士の演算です.") return Modulo(self.a+other.a,self.n) elif isinstance(other,int): return Modulo(self.a+other,self.n) def __radd__(self,other): if isinstance(other,int): return Modulo(self.a+other,self.n) #減法 def __sub__(self,other): return self+(-other) def __rsub__(self,other): if isinstance(other,int): return -self+other #乗法 def __mul__(self,other): if isinstance(other,Modulo): if self.n!=other.n: raise Modulo_Error("異なる法同士の演算です.") return Modulo(self.a*other.a,self.n) elif isinstance(other,int): return Modulo(self.a*other,self.n) def __rmul__(self,other): if isinstance(other,int): return Modulo(self.a*other,self.n) #Modulo逆数 def inverse(self): return self.Modulo_Inverse() def Modulo_Inverse(self): x0, y0, x1, y1 = 1, 0, 0, 1 a,b=self.a,self.n while b != 0: q, a, b = a // b, b, a % b x0, x1 = x1, x0 - q * x1 y0, y1 = y1, y0 - q * y1 if a!=1: raise Modulo_Error("{}の逆数が存在しません".format(self)) else: return Modulo(x0,self.n) #除法 def __truediv__(self,other): return self*(other.Modulo_Inverse()) def __rtruediv__(self,other): return other*(self.Modulo_Inverse()) #累乗 def __pow__(self,m): u=abs(m) r=Modulo(pow(self.a,u,self.n),self.n) if m>=0: return r else: return r.Modulo_Inverse() #法の合成 def __modulo_composite__(p,q): from math import gcd a,n=p.a,p.n b,m=q.a,q.n d=b-a g,h=n,m while h: g,h=h,g%h if d%g: raise Modulo_Error("{}と{}は両立しません.".format(p,q)) n//=g m//=g d//=g s=(Modulo(1,m)/Modulo(n,m)).a return Modulo(a+(n*g)*d*s,n*m*g) def Modulo_Composite(*X): from functools import reduce return reduce(__modulo_composite__,X) #================================================= alpha=167772161 beta =469762049 gamma=1224736769 K=int(input()) N=int(input()) X=list(map(int,input().split())) L=[0]*(K+1) for x in X: if x<=K: L[x]+=1 A=[] for Mod in [alpha,beta,gamma]: P=Modulo_Polynominal(L,K+1) Q=1/(1-P) A.append(Modulo(Q.coefficient(K),Mod)) B=Modulo_Composite(*A).a print(B%(10**9+7))