結果
| 問題 |
No.8046 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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 4 WA * 1 TLE * 4 |
ソースコード
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))