思路
首先有个挺显然的DP
[dp[i][(j*k)\%m]+=dp[i-1][j] imes dp[i-1][k]
]
想办法优化这个DP
这个dp也可以写成这样
[dp[i][j]=sum_{p*q=j}dp[i-1][p] imes dp[i-1][q]
]
看着一副卷积的样子
但是是乘法，可以考虑转化乘法为加法，有两种方式，取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
",b[pos[x]]);
return 0;
}