感觉这个题挺妙的......
考虑最暴力的\(dp\)，令\(f[i][j]\)表示生成大小为\(i\)的序列，积为\(j\)的方案数，这样做是\(O(nm)\)的。
转移就是
\[
f[i+1][j] = \sum\limits_{ab\equiv j(mod\ m)} f[i][a]f[1][b]
\]
后面那个柿子很像卷积？但下标是乘法......好像不那么好卷。
套路的去个对数啥的把他转化成加法？比方说取个ln
那底数怎么确定呢？
我们想把\(1...m-1\)这\(m-1\)个数通过取对数的方法映射到\(1,2,...m-1\)这些不同的数上。
咋办？以原根为底就好辣！（下面默认\(m\)原根是\(g\)，\(\log a = \log_{g} a\)）。
因为根据定义我们知道\(g^{m-1} \equiv 1\ (mod \ m)\)，且\(g^0,g^1,\cdots,g^{m-2}\)是\(m-1\)个不同的数。
所以在上面的\(dp\)转移中，我们令\(A = \log a, B = \log b, C = \log j\)，然后再改一下状态，转移就变成了
\[
f[i+1][C] = \sum\limits_{A+B=C} f[i][A]f[1][B]
\]
这样一阶段的转移就是卷积的形式，且转移方式是相同的。
但是\(n\)很大.......因为转移的特殊性，我们可以类似快速幂那样倍增（有点像矩乘？）
具体边界还有一些要注意的地方就看代码吧：
#include <bits/stdc++.h>
using namespace std;
const int N=20100,P=1004535809,gen=3,igen=334845270;
inline int add(int x,int y,int mod=P){
return x+y>=mod?x+y-mod:x+y;
}
inline int sub(int x,int y,int mod=P){
return x-y<0?x-y+mod:x-y;
}
inline int fpow(int x,int y,int mod=P){
int ret=1; for(x%=mod;y;y>>=1,x=1ll*x*x%mod)
if(y&1) ret=1ll*ret*x%mod;
return ret;
}
int rev[N];
void init(int n){
for(int i=0;i<n;i++)
rev[i]=rev[i>>1]>>1|((i&1)?n>>1:0);
}
void ntt(int *f,int n,int flg){
for(int i=0;i<n;i++) if(rev[i]<i) swap(f[i],f[rev[i]]);
for(int len=2,k=1;len<=n;len<<=1,k<<=1){
int wn=fpow(flg==1?gen:igen,(P-1)/len);
for(int i=0;i<n;i+=len){
for(int w=1,j=i;j<i+k;j++,w=1ll*w*wn%P){
int tmp=1ll*f[j+k]*w%P;
f[j+k]=sub(f[j],tmp),f[j]=add(f[j],tmp);
}
}
}
if(flg==-1){
int inv=fpow(n,P-2);
for(int i=0;i<n;i++) f[i]=1ll*f[i]*inv%P;
}
}
int limit,m,n,X,C;
void mult(int *f,int *g){
static int F[N],G[N];
for(int i=0;i<m-1;i++) F[i]=f[i],G[i]=g[i];
for(int i=m-1;i<limit;i++) F[i]=G[i]=0;
ntt(F,limit,1),ntt(G,limit,1);
for(int i=0;i<limit;i++) F[i]=1ll*F[i]*G[i]%P;
ntt(F,limit,-1);
for(int i=0;i<m-1;i++) f[i]=add(F[i],F[i+m-1]); // 这里挺重要的qwq，因为卷起来后次数是2(m-1)的，又因为m-1一个循环，要加上去
}
int chk(int g){
for(int i=2;i*i<=m-1;i++)
if((m-1)%i==0&&(fpow(g,i,m)==1||fpow(g,(m-1)/i,m)==1)) return 0;
return 1;
}
int getG(){
for(int i=2;;i++) if(chk(i))return i;
}
map<int,int> id;
void getans(int *f,int n,int *ans){
for(ans[id[1]]=1;n;n>>=1,mult(f,f)) // 一开始的时候只有f[0][1]是1
if(n&1) mult(ans,f);
}
int f[N],ans[N];
int main(){
scanf("%d%d%d%d",&n,&m,&X,&C);
limit=1; while(limit<=m*2)limit<<=1; init(limit);
int g=getG(); // m的原根
for(int i=0;i<m-1;i++)id[fpow(g,i,m)]=i;
for(int i=1;i<=C;i++){
int x; scanf("%d",&x),x%=m;
if(x) f[id[x]]=1;
}
getans(f,n,ans);
printf("%d\n",ans[id[X]]);
return 0;
}[题解] LuoguP3321 [SDOI2015]序列统计
原文：https://www.cnblogs.com/wxq1229/p/12291091.html