题目
题目描述
小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为，两个数列{Ai}和{Bi}不同，当且仅当至少存在一个整数i，满足Ai≠Bi。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案mod 1004535809的值就可以了。
输入输出格式
输入格式：
一行，四个整数，N、M、x、$\vert S\vert$，其中$\vert S\vert$为集合S中元素个数。第二行，$\vert S\vert$个整数，表示集合S中的所有元素。
输出格式：
一行，一个整数，表示你求出的种类数mod 1004535809的值。
输入输出样例
输入样例#1：
4 3 1 2
1 2
输出样例#1：
8
说明
【样例说明】
可以生成的满足要求的不同的数列有(1,1,1,1)、(1,1,2,2)、(1,2,1,2)、(1,2,2,1)、(2,1,1,2)、(2,1,2,1)、(2,2,1,1)、(2,2,2,2)。
【数据规模和约定】
对于10%的数据，1<=N<=1000；
对于30%的数据，3<=M<=100；
对于60%的数据，3<=M<=800；
对于全部的数据，1<=N<=10^9，3<=M<=8000，M为质数，1<=x<=M-1，输入数据保证集合S中元素不重复
题解
感觉挺神仙的……
首先最简单的$dp$方程推出来：$f_{i,j\times S_k\%M}+=f_{i-1,j}$，时间复杂度是$O(NM\vert S\vert )$的
发现每一步的转移都一样，可以用快速幂优化，时间复杂度是$O(M^2\log n)$
现在瓶颈在$M^2$了
发现$dp$方程是$f_i\times f_j=f_{ij}$
是个积性函数！
如果是$f_i\times f_j=f_{i+j}$的话就好做多了，可以卷积了
因为$x^i\times x^j=x^{i+j}$
所以可以把下标转换成某个数的多少次幂，并且$0\rightarrow M-1$都能被这个数的次幂表示
$M$的原根？
但是$M$可能没有原根，并且原根表示不了$0$……
似乎有性质被忽略了？
$M$为质数，且$1\le x\le M-1$
这样问题就迎刃而解了，因为要模数要用$NTT$了
代码
# include<iostream>
# include<cstring>
# include<cstdio>
# include<cmath>
# include<algorithm>
using namespace std;
const int MAX=1e5+5,mod=1004535809;
int n,m,X,N,lim=1,L;
int a[MAX],b[MAX],f[MAX],F[MAX],R[MAX],S[MAX],id[MAX],pm[MAX];
int read()
{
int x(0);
char ch=getchar();
for(;!isdigit(ch);ch=getchar());
for(;isdigit(ch);x=x*10+ch-48,ch=getchar());
return x;
}
int Pow(int a,int b,int Mod=mod)
{
int ans=1;
for(;b;b>>=1,a=1ll*a*a%Mod)
if(b&1) ans=1ll*ans*a%Mod;
return ans;
}
void NTT(int *A,int tt=1)
{
for(int i=0;i<lim;++i)
if(i<R[i]) swap(A[i],A[R[i]]);
for(int i=1,G1;i<lim;i<<=1)
{
G1=Pow(3,(mod-1)/(i<<1));
for(int l=i<<1,G,j=0;j<lim;j+=l)
{
G=1;
for(int k=0,x,y;k<i;++k,G=1ll*G1*G%mod)
{
x=A[j+k],y=1ll*G*A[i+j+k]%mod,A[j+k]=x+y,A[i+j+k]=x-y+mod;
if(A[j+k]>=mod) A[j+k]-=mod;
if(A[i+j+k]>=mod) A[i+j+k]-=mod;
}
}
}
if(tt==-1)
{
reverse(A+1,A+lim);
for(int i=0,G=Pow(lim,mod-2);i<lim;++i)
A[i]=1ll*A[i]*G%mod;
}
}
int GET_ROOT()
{
int N=m-1,tot=0,G=-1;
for(int i=2;i<=sqrt(N);++i)
if(N%i==0)
{
pm[++tot]=i;
while(N%i==0) N/=i;
}
if(N>1) pm[++tot]=N;
for(int i=2;i<m;++i)
{
bool fl=0;
for(int j=1;j<=tot;++j)
if(Pow(i,(m-1)/pm[j],m)==1) {fl=1;break;}
if(!fl) {G=i;break;}
}
return G;
}
void GET_ARR()
{
int G=GET_ROOT();
for(int i=0;i<m-1;++i)
id[Pow(G,i,m)]=i;
}
void Calc(int *A,int *B,int *C,bool fl=0)
{
memset(a,0,sizeof(a));
memset(b,0,sizeof(b));
for(int i=0;i<m-1;++i)
a[i]=A[i],b[i]=B[i];
NTT(a),NTT(b);
for(int i=0;i<=lim;++i)
a[i]=1ll*a[i]*b[i]%mod;
NTT(a,-1);
for(int i=0;i<m-1;++i)
{
C[i]=a[i]+a[i+m-1];
if(C[i]>=mod) C[i]-=mod;
}
}
int main()
{
n=read(),m=read(),X=read(),N=read(),GET_ARR();
for(int i=1,x;i<=N;++i)
{
x=read();
if(x) ++f[id[x]];
}
while(lim<=2*(m-2)) lim<<=1,++L;
for(int i=0;i<lim;++i)
R[i]=(R[i>>1]>>1)|((i&1)<<L-1);
F[id[1]]=1;
for(int b=n;b;b>>=1,Calc(f,f,f))
if(b&1) Calc(F,f,F);
return printf("%d",F[id[X]]),0;
}
