【BZOJ3992】[SDOI2015]序列统计
Description
小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。
小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为，两个数列{Ai}和{Bi}不同，当且仅当至少存在一个整数i，满足Ai≠Bi。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案mod 1004535809的值就可以了。
Input
一行，四个整数，N、M、x、|S|，其中|S|为集合S中元素个数。第二行，|S|个整数，表示集合S中的所有元素。
Output
一行，一个整数，表示你求出的种类数mod 1004535809的值。
Sample Input
4 3 1 2
1 2
1 2
Sample Output
8
HINT
【样例说明】
可以生成的满足要求的不同的数列有(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<=109，3<=M<=8000，M为质数，1<=x<=M-1，输入数据保证集合S中元素不重复
题解：如果你早已深入理解生成函数，可以无视下面这段话：
“未学生成函数的时候，以为这种题就是将两个桶相乘，得到一个新的桶，桶里装的是方案数。了解生成函数后，发现就是讲桶中的每一位都看成多项式中的一个系数，然后用多项式的运算法则来优化运算的过程，最后的答案依旧是其中的一位系数。如果像我一样对生成函数了解较少的话，可以先考虑DP，用DP方程将式子列出来，然后将整个DP数组看成一个大多项式，继续推下去就好。”
如果你早已深入理解NTT，可以无视下面这段话：
“NTT与FFT的区别是：FFT利用的是e的特性，将系数表达式与点值表达式进行快速的转换，而在NTT中，模数的原根正好有同样的性质，并且常见的就是998244353的一个原根=3。于是，只需要将单位复数根变成3的幂次，除法改成逆元，其余都一样了。”
如果你早已理解原根与指标，可以无视下面这段话：
“如果x^0,x^1,...x^n-1在mod n意义下正好覆盖了0-n-1中的所有数，则x是n的一个原根，他的意义可以看成是模意义下的e。而指标的意义，可以看成是模意义下的取ln。这两个东西在本题中的意义就是将乘法转变成加法。
“原根的求法：暴力枚举x，如果x对于$\varphi(p)$的所有质因子pi，都有$x^{\varphi(p) \over pi} \neq 1$，则x是p的原根。
“指标的求法：如果原根是r，则r^x的指标即为x。"
回到本题，我们将原数组求指标后，将得到的多项式^n即可，可以用多项式的快速幂实现。
#include <cstdio>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;
const ll P=1004535809ll;
const ll G=3;
const int maxn=100010;
int n,m,X,S,root,num,len;
ll pri[maxn],A[maxn],B[maxn];
ll s[maxn],ind[maxn];
inline int rd()
{
int ret=0,f=1; char gc=getchar();
while(gc<'0'||gc>'9') {if(gc=='-')f=-f; gc=getchar();}
while(gc>='0'&&gc<='9') ret=ret*10+gc-'0',gc=getchar();
return ret*f;
}
ll pm(ll x,ll y,ll z)
{
ll ret=1;
while(y)
{
if(y&1) ret=ret*x%z;
x=x*x%z,y>>=1;
}
return ret;
}
void get_factor(ll x)
{
for(ll i=2;i*i<=x;i++)
{
if(x%i==0)
{
pri[++num]=i;
while(x%i==0) x/=i;
}
}
if(x!=1) pri[++num]=x;
}
bool check(ll x)
{
for(int i=1;i<=num;i++) if(pm(x,(m-1)/pri[i],m)==1) return 0;
return 1;
}
ll get_root(ll x)
{
ll tmp=x-1;
get_factor(tmp);
for(ll i=2;i<=tmp;i++) if(check(i)) return i;
return 0;
}
void NTT(ll *a,int f)
{
int i,j,k,h;
ll t;
for(i=k=0;i<len;i++)
{
if(i>k) swap(a[i],a[k]);
for(j=len>>1;(k^=j)<j;j>>=1);
}
for(h=2;h<=len;h<<=1)
{
ll wn=pm(G,f==1?(P-1)/h:P-1-(P-1)/h,P);
for(j=0;j<len;j+=h)
{
ll w=1;
for(k=j;k<j+h/2;k++) t=w*a[k+h/2]%P,a[k+h/2]=(a[k]-t+P)%P,a[k]=(a[k]+t)%P,w=w*wn%P;
}
}
if(f==-1)
{
t=pm(len,P-2,P);
for(i=0;i<len;i++) a[i]=a[i]*t%P;
}
}
void POW(ll *b,ll y)
{
ll *a=B;
a[0]=1;
while(y)
{
NTT(b,1);
if(y&1)
{
NTT(a,1);
for(int i=0;i<len;i++) a[i]=a[i]*b[i]%P;
NTT(a,-1);
for(int i=len-1;i>=m-1;i--) a[i-m+1]=(a[i-m+1]+a[i])%P,a[i]=0;
}
for(int i=0;i<len;i++) b[i]=b[i]*b[i]%P;
NTT(b,-1);
for(int i=len-1;i>=m-1;i--) b[i-m+1]=(b[i-m+1]+b[i])%P,b[i]=0;
y>>=1;
}
}
int main()
{
n=rd(),m=rd(),X=rd(),S=rd();
int i;
for(i=1;i<=S;i++) s[i]=rd();
root=get_root(m);
ll tmp=1;
for(i=0;i<m-1;i++) ind[tmp]=i,tmp=tmp*root%m;
for(len=1;len<=m+m;len<<=1);
for(i=1;i<=S;i++) if(s[i]) A[ind[s[i]]]=1;
POW(A,n);
printf("%lld\n",B[ind[X]]);
return 0;
}