为啥只有我和CuFeO4【数据删除】，别人都没【数据删除】，血亏，下次绝对不【数据删除】了
明天有CF，希望能打
在写\(\text{NTT}\)惹，但是没有达成写4题呜呜
明天有模拟赛
唔，首先是朴素 \(dp\) 骗分，设 \(dp_{i,j}\) 表示已经取到了 \(i\) 个，其中取模后结果为 \(j\) 的方案数，容易有转移
\[dp_{i+j,z}=\sum_{x*y\equiv z\pmod{p}}dp_{i,y}*dp_{j,x} \]复杂度似乎是明显的\(O(nm^2)\)，能有\(10\text{pts}\)似乎不错了
然后发现可以倍增优化，转移方程变为
\[dp_{2\times i,z}=\sum_{x*y\equiv z\pmod{p}}dp_{i,y}*dp_{i,x} \]复杂度\(O(m^2 \log n)\)似乎用处不大啊
但是这是\(\text{NTT}\)题单的题啊，所以必然要用\(\text{NTT}\)来加速的
上面那依托东西可以看做这个
\[c_{z}=\sum_{x*y\equiv z\pmod p}a_{x}b_{y} \]如果能转化成下面的式子就可以 \(\text{NTT}\) 了嗯哼
\[c_{z}=\sum_{x*y\equiv z\pmod p}a_{x}b_{y} \]但是我不太会，看了题解说可以转化成 \(\log\) 很奇怪
\[c_{\log_gz}=\sum_{\log _gx+\log _gy\equiv log_gz\pmod p}a_{\log_gx}+b_{\log_gy} \]然后不就随便搞了呜
『你应该忘记了吧/天气晴朗/心里却潮湿的盛夏』
const int mod=1004535809;
int n,m,X,S,tot,cnt,rev[N],g,gg,a[N],b[N],res[N],f[N],top,fact[N];
map<int,int>mp;
inline int qpow(int x,int y,int p){
int res=1;
for(;y;y>>=1,x=x*x%p)
if(y&1)res=res*x%p;
return res;
}
inline int Get(int x){
top=0;
int rem=x-1,p=rem;
for(int i=2;i*i<=x;i++)
if(!(rem%i)){
fact[++top]=i;
while(!(rem%i))rem/=i;
}
if(rem>1) fact[++top]=rem;
for(int flag=1,i=2;i<=p;i++,flag=1){
for(int j=1;j<=top&&flag;j++)
if(qpow(i,p/fact[j],x)==1) flag=0;
if(flag) return i;
}
return -1;
}
inline void NTT(int *p,int opt){
for(int i=0;i<tot;i++) if(i<rev[i]) swap(p[i],p[rev[i]]);
for(int i=1;i<tot;i<<=1){
int rt=qpow(opt==1?g:gg,(mod-1)/(i<<1),mod);
for(int j=0;j<tot;j+=(i<<1)){
int w=1;
for(int k=j;k<j+i;k++,w=w*rt%mod){
int x=p[k],y=w*p[k+i]%mod;
p[k]=(x+y)%mod,p[k+i]=(x-y+mod)%mod;
}
}
}
if(opt==-1){
int inv=qpow(tot,mod-2,mod);
for(int i=0;i<tot;i++) a[i]=a[i]*inv%mod;
}
}
inline void mul(int *A,int *B,int *C){
for(int i=0;i<tot;i++)
a[i]=A[i],b[i]=B[i];
NTT(a,1),NTT(b,1);
for(int i=0;i<tot;i++)
a[i]=a[i]*b[i]%mod;
NTT(a,-1);
for(int i=0;i<m-1;i++)
a[i]=(a[i]+a[i+m-1])%mod,
a[i+m-1]=0;
for(int i=0;i<tot;i++)
C[i]=a[i];
}
signed main(){
FastI>>n>>m>>X>>S;
g=Get(m),gg=qpow(g,m-2,m);
for(int tmp=1,i=0;i<m-1;i++,tmp=tmp*g%m)
mp[tmp]=i;
for(int x,i=1;i<=S;i++){
FastI>>x;
if(x)
f[mp[x]]++;
}
res[mp[1]]=1;
for(tot=1;tot<=2*m;tot<<=1)
cnt++;
cnt--;
for(int i=0;i<tot;i++)
rev[i]=(rev[i>>1]>>1)|((i&1)<<cnt);
g=Get(mod),gg=qpow(g,mod-2,mod);
while(n){
if(n&1)
mul(res,f,res);
mul(f,f,f);
n>>=1;
}
FastO<<res[mp[X]];
}
然后是最短母串，一道AC自动机+状压dp的好题，但是因为越界了所以调了好久导致鲜花没时间写了，血亏
