#589202 (PyPy3) No.8046 yukicoderの過去問

• 問題: 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

入力	結果	実行時間; 実行使用メモリ
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))