3992: [SDOI2015]序列統計
【題目描述】
傳送門
【題解】
我們可以寫出DP式， F [ i ] [ j ∗ a [ k ] ] + = F [ i − 1 ] [ j ] F[i][j*a[k]]+=F[i-1][j] F[i][j∗a[k]]+=F[i−1][j]
初始狀态 F [ 0 ] [ 0 ] = 1 F[0][0]=1 F[0][0]=1
對于上式我們很難處理，如果我們可以将相乘改成相加，就可以套NTT了。
我們設 g g g為mod m意義下的原根。
設 j = g b j j=g^{bj} j=gbj， a [ k ] = g b a [ k ] a[k]=g^{ba[k]} a[k]=gba[k]
上式就可以寫成 F [ i ] [ g b j + b a [ k ] ] + = F [ i − 1 ] [ g b j ] F[i][g^{bj+ba[k]}]+=F[i-1][g^{bj}] F[i][gbj+ba[k]]+=F[i−1][gbj]
也就是 F [ i ] [ b j + b a [ k ] ] + = F [ i − 1 ] [ b j ] F[i][bj+ba[k]]+=F[i-1][bj] F[i][bj+ba[k]]+=F[i−1][bj]
這不就是卷積的形式了嗎，直接套NTT就可以了
【代碼如下】
#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=8005,MOD=1004535809;
int Len,lg2,g,inv,pos,T,m,X,n,rev[MAXN<<2],Mu[MAXN<<2],a[MAXN<<2],F[MAXN<<2],G[MAXN<<2],NI;bool vis[MAXN];
int qsm(int x,int b,int p){
int Mul=1;
for(;b;b>>=1,x=1ll*x*x%p) if(b&1) Mul=1ll*Mul*x%p;
return Mul;
}
int Cal(){//求m的原根
if(m==2) return 1;
for(int i=2;;i++){
bool f=1;
for(int j=2;j*j<m;j++)
if(qsm(i,(m-1)/j,m)==1){f=0;break;}
if(f) return i;
}
}
void Getrev(){for(int i=0;i<Len;i++) rev[i]=(rev[i>>1]>>1)|((i&1)<<(lg2-1));}
void NTT(int *A,int opt){
for(int i=0;i<Len;i++) if(i<rev[i]) swap(A[i],A[rev[i]]);
for(int i=1;i<Len;i<<=1){
int WN=qsm((opt==1?3:inv),(MOD-1)/(i<<1),MOD);
for(int j=0;j<Len;j+=i<<1)
for(int k=0,W=1;k<i;k++,W=1ll*W*WN%MOD){
int x=A[j+k],y=1ll*W*A[j+k+i]%MOD;
A[j+k]=(x+y)%MOD;A[j+k+i]=(x-y+MOD)%MOD;
}
}
if(opt==-1) for(int i=0;i<Len;i++) A[i]=1ll*A[i]*NI%MOD;
}
void Mul(int *A,int *B){
for(int i=0;i<Len;i++) F[i]=A[i];
for(int i=0;i<Len;i++) G[i]=B[i];
NTT(G,1),NTT(F,1);
for(int i=0;i<Len;i++) F[i]=1ll*F[i]*G[i]%MOD;
NTT(F,-1);
for(int i=0;i<m-1;i++) A[i]=(F[i]+F[i+m-1])%MOD;
}
void Solve(){for(Mu[0]=1;T;T>>=1,Mul(a,a)) if(T&1) Mul(Mu,a);}
int main(){
scanf("%d%d%d%d",&T,&m,&X,&n);
for(int i=1,x;i<=n;i++) scanf("%d",&x),vis[x]=1;
g=Cal();
for(int i=0,x=1;i<m-1;i++,x=x*g%m){if(vis[x]) a[i]=1;if(x==X) pos=i;}
for(Len=1,lg2=0;Len<=(m-1<<1);Len<<=1,lg2++);
NI=qsm(Len,MOD-2,MOD);inv=qsm(3,MOD-2,MOD);Getrev();Solve();
printf("%d\n",Mu[pos]);
return 0;
}