思路

首先有个挺显然的DP

想办法优化这个DP

这个dp也可以写成这样

看着一副卷积的样子

但是是乘法，可以考虑转化乘法为加法，有两种方式，取ln或者原根

注意到m是质数，所以取原根，每层之间的转移就变成卷积了

但是这题的卷积下标是模m的，所以每次乘完都要把大于m-1的加到对应项上（i+m-1和i对应）所以好像不能直接多项式快速幂

n是\(10^9\)，上个类似快速幂的倍增即可

复杂度是\(O(m \log m \log n)​\)

代码

#include <cstdio>

#include <algorithm>

#include <cstring>

#include <queue>

#include <cmath>

#define int long long

using namespace std;

const int MOD = 1004535809;

const int G = 3;

const int invG = 334845270;

const int MAXN = 140000;

namespace getG{

    int q[100000],cnt=0;

    int phi(int n){

        int ans=n;

        int m=(int)sqrt(n+0.5);

        for(int i=2;i<=m;i++){

            if(n%i==0){

                ans=ans/i*(i-1);

                while(n%i==0)

                    n/=i;

            }

        }

        if(n>1)

            ans=ans/n*(n-1);

        return ans;

    }

    int my_pow(int a,int b,int mod){

        int ans=1;

        while(b){

            if(b&1)

                ans=(1LL*ans*a)%mod;

            a=(1LL*a*a)%mod;

            b>>=1;

        }

        return ans;

    }

    int G(int m){

        int Phi = phi(m);

        int sq=sqrt(Phi),mid=Phi;

        for(int i=2;i<=sq;i++)

            if(mid%i==0){

                q[++cnt]=Phi/i;

                while(mid%i==0)

                    mid/=i;

            }

        if(mid>1)

            q[++cnt]=Phi/mid;

        for(int g=2;1;g++){

            int f=true;

            if(my_pow(g,Phi,m)!=1)

                continue;

            else

                for(int j=1;j<=cnt;j++){

                    if(my_pow(g,q[j],m)==1){

                        f=false;

                        break;

                    }

                }

            if(f)

                return g;

        }

    }

};

int rev[MAXN];

int my_pow(int a,int b){

    int ans=1;

    while(b){

        if(b&1)

            ans=(1LL*ans*a)%MOD;

        a=(1LL*a*a)%MOD;

        b>>=1;

    }

    return ans;

}

void cal_rev(int n,int lim){

    for(int i=0;i<n;i++)

        rev[i]=(rev[i>>1]>>1)|((i&1)<<(lim-1));

}

void NTT(int *a,int opt,int n,int lim){

    for(int i=0;i<n;i++)

        if(i<rev[i])

            swap(a[i],a[rev[i]]);

    for(int i=2;i<=n;i<<=1){

        int len=i/2;

        int tmp=my_pow((opt)?G:invG,(MOD-1)/i);

        for(int j=0;j<n;j+=i){

            int arr=1;

            for(int k=j;k<j+len;k++){

                int t=(1LL*a[k+len]*arr)%MOD;

                a[k+len]=(a[k]-t+MOD)%MOD;

                a[k]=(a[k]+t)%MOD;

                arr=(1LL*arr*tmp)%MOD;

            }

        }

    }

    if(!opt){

        int invN = my_pow(n,MOD-2);

        for(int i=0;i<n;i++)

            a[i]=(1LL*a[i]*invN)%MOD;

    }

}

void mul(int *a,int *b,int &at,int bt){

    int num=(at+bt),n=1,lim=0;

    while(n<=(num+2))

        n<<=1,lim++;

    cal_rev(n,lim);

    static int tmp[MAXN];

    for(int i=0;i<n;i++)

        tmp[i]=b[i];

    NTT(a,1,n,lim);

    NTT(tmp,1,n,lim);

    for(int i=0;i<n;i++)

        a[i]=(1LL*a[i]*tmp[i])%MOD;

    NTT(a,0,n,lim);

    at+=bt;

}

void sqr(int *a,int &at){

    int num=(at+at),n=1,lim=0;

    while(n<=(num+2))

        n<<=1,lim++;

    cal_rev(n,lim);

    static int tmp[MAXN];

    for(int i=0;i<n;i++)

        tmp[i]=a[i];

    NTT(tmp,1,n,lim);

    for(int i=0;i<n;i++)

        a[i]=(1LL*tmp[i]*tmp[i])%MOD;

    NTT(a,0,n,lim);

    at=num;

}

void my_pow(int *a,int *b,int n,int m,int k){

    static int tmp[MAXN];

    for(int i=0;i<=n;i++)

        tmp[i]=a[i];

    b[0]=1;

    int bt=m-1;

    while(k){

        if(k&1){

            mul(b,tmp,bt,n);

            for(int i=0;i<m;i++){

                b[i]=(b[i]+b[i+m-1])%MOD;

                b[i+m-1]=0;

            }

            for(int i=m;i<=bt;i++)

                b[i]=0;

            bt=m-1;

        }

        sqr(tmp,n);

        for(int i=0;i<m;i++){

            tmp[i]=(tmp[i]+tmp[i+m-1])%MOD;

            tmp[i+m-1]=0;

        }

        for(int i=m;i<=n;i++)

            tmp[i]=0;

        n=m-1;

        k>>=1;

    }

}

int n,m,pos[MAXN],S,x,a[MAXN],b[MAXN];

signed main(){

    scanf("%lld %lld %lld %lld",&n,&m,&x,&S);

    int g=getG::G(m);

    for(int i=1,t=1;i<=m-2;i++){

        t=(1LL*t*g)%m;

        pos[t]=i;

    }

    for(int i=1;i<=S;i++){

        int midx;

        scanf("%lld",&midx);

        if(midx)

            a[pos[midx]]=1;

    }

    my_pow(a,b,m-1,m,n);

    printf("%lld\n",b[pos[x]]);

    return 0;

}