zcmimi's blog
avatar
zc
2020-07-07 17:25:00
  • 本文总阅读量
查看原题

点击跳转

首先了解原根

这里利用到原根的一个性质:

gm的一个原根
g^0,g^1,g^2,\dots,g^{\varphi(m)-1}构成模m的简化剩余系

这样我们可以把序列中所有数变成原根的次幂,

那么序列中所有数的乘积就可以转化为他们的和

设这个和为sum

设生成函数:\displaystyle f(x)=\sum_{i=0}^m [i\in S]x^i

可以发现f(x)^n次数为sum的那一项的系数就是答案

使用快速幂+快速数论变换

#include<bits/stdc++.h>
const int N=3000010,P=1004535809,G=3,Gi=334845270;
int n,m,X,S,f[N],F[N],l,r[N],b[N],L;
void mod(int&x){if(x>=P)x-=P;}
void swap(int&x,int&y){x^=y,y^=x,x^=y;}
int pw(int x,int b,int p=P){
    int res=1;
    while(b){
        if(b&1)res=1ll*res*x%p;
        b>>=1;x=1ll*x*x%p;
    }
    return res;
}
void ntt(int*A,int typ){
    for(int i=0;i<L;++i)
        if(i<r[i])swap(A[i],A[r[i]]);
    for(int len=1;len<L;len<<=1){
        int Wn=pw(~typ?G:Gi,(P-1)/(len<<1));
        for(int i=0;i<L;i+=len<<1){
            int w=1;
            for(int k=0;k<len;++k){
                int t=1ll*w*A[i+k+len]%P;
                mod(A[i+k+len]=A[i+k]-t+P);
                mod(A[i+k]+=t);
                w=1ll*w*Wn%P;
            }
        }
    }
    if(~typ)return;
    int inv=pw(L,P-2);
    for(int i=0;i<L;++i)
        A[i]=1ll*A[i]*inv%P;
}
int a[N],tt;
int getg(){
    for(int i=2;i<=m-2;++i)
        if((m-1)%i==0)a[++tt]=i;
    for(int i=2;;++i){
        bool ff=1;
        for(int j=1;j<=tt;++j)
            if(pw(i,a[j],m)==1){ff=0;break;}
        if(ff)return i;
    }
}
int main(){
    scanf("%d%d%d%d",&n,&m,&X,&S);
    for(int i=1,x=1,g=getg();i<=m-2;++i)
        b[x=1ll*x*g%m]=i;
    for(int i=1,t;i<=S;++i){
        scanf("%d",&t);
        if(t)F[b[t]]=1;
    }

    for(L=1;L<m;L<<=1,++l);
    L<<=1,++l;

    for(int i=0;i<L;++i)
        r[i]=(r[i>>1]>>1)|((i&1)<<(l-1));
    f[0]=1;
    while(n){
        ntt(F,1);
        if(n&1){
            ntt(f,1);
            for(int i=0;i<L;++i)
                f[i]=1ll*f[i]*F[i]%P;
            ntt(f,-1);
            for(int i=L-1;i>=m-1;--i)
                mod(f[i-m+1]+=f[i]),f[i]=0;
        }
        n>>=1;
        for(int i=0;i<L;++i)
            F[i]=1ll*F[i]*F[i]%P;
        ntt(F,-1);
        for(int i=L-1;i>=m-1;--i)
            mod(F[i-m+1]+=F[i]),F[i]=0;
    }
    printf("%d\n",f[b[X]]);
}
LG 3321 [SDOI2015]序列统计
comment评论
Search
search