BZOJ 3992: [SDOI2015]序列统计
标签（空格分隔）： OI BZOJ NTT
Time Limit: 30 Sec
Memory Limit: 128 MB
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
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中元素不重复
Source
Round 1 感谢yts1999上传
Solution####
通过原根化乘为加，求出m的原根g。
对于每个ai求出(g^{b_i}=a_i)。
则有 (prodlimits_{i=1}^{N}{a_i}=g^{sumlimits_{i=1}^{N}{b_i}})。
我们求出母函数$$f(x)=(prod_{i=1}N(x{b_i}+1) )pmod {x^{M-1}}$$
设(g^k=X)
问题就变成了求(f(x))的第k项,做一遍FNTT即可。
1004535809的原根是3。
Code####
#include<iostream>
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<math.h>
#include<algorithm>
#include<queue>
#include<set>
#include<map>
#include<bitset>
#include<vector>
using namespace std;
#define LL long long
const int maxn=14;
int mod=1004535809;
int n,N,M,X,S;
LL gg;
LL A[1<<maxn],B[1<<maxn];
LL ww[1<<maxn+1],*e=ww+(1<<maxn),h[1<<maxn];
int fg[10000];
struct mul
{
LL s[1<<maxn];
}f0,f;
LL ksm(LL a,int b,int mod)
{
LL ans=1;
for(;b;b>>=1,a=a*a%mod)
if(b&1)
ans=ans*a%mod;
return ans;
}
int findg(int s)
{
int q[1000]={0};
for(int i=2;i<s-1;i++)
if((s-1)%i==0)
q[++q[0]]=i;
for(int i=2;;i++)
{bool p=1;
for(int j=1;j<=q[0]&&p;j++)
if(ksm(i,q[j],s)==1)
p=0;
if(p)return i;
}
return -1;
}
void DFT(LL *x,int n,int c)
{
LL *a=x,*b=h,w,l,r;
int i,j,k;
for(i=n;i>1;i>>=1,swap(a,b))
for(j=0;j<n;j+=i)
for(k=0;k<i;k+=2)
b[j+(k>>1)]=a[j+k],b[j+(k>>1)+(i>>1)]=a[j+k+1];
for(i=2;i<=n;i<<=1,swap(a,b))
for(w=0,k=0;k<(i>>1);k++,w+=n/i*c)
for(j=0;j<n;j+=i)
{l=a[j+k],r=e[w]*a[j+(i>>1)+k]%mod;
b[j+k]=((l+r>=mod)?l+r-mod:l+r);
b[j+(i>>1)+k]=((l-r<0)?l-r+mod:l-r);
}
for(int i=0;i<n;i++)
x[i]=a[i];
}
void plu(LL *x,mul A,mul B)
{
DFT(A.s,n,1);DFT(B.s,n,1);
for(int i=0;i<n;i++)
A.s[i]=A.s[i]*B.s[i]%mod;
DFT(A.s,n,-1);
int ni=ksm(n,mod-2,mod);
for(int i=0;i<M-1;i++)
x[i]=0;
for(int i=0;i<n;i++)
x[i%(M-1)]+=A.s[i]*ni,x[i%(M-1)]%=mod;
}
int main()
{
scanf("%d%d%d%d",&N,&M,&X,&S);
gg=findg(M);
LL ss=1;
for(int i=1;i<M-1;i++)
ss=ss*gg%M,
fg[ss]=i;
for(int i=1,x;i<=S;i++)
{scanf("%d",&x);
if(x)f0.s[fg[x]]=1;
}
for(n=1;n<=M*2;n<<=1);
e[0]=e[-n]=1;e[1]=e[1-n]=ksm(3,(mod-1)/n,mod);
for(int i=2;i<n;i++)e[i-n]=e[i]=e[i-1]*e[1]%mod;
for(f.s[0]=1;N;N>>=1,plu(f0.s,f0,f0))
if(N&1)
plu(f.s,f,f0);
printf("%d
",int(f.s[fg[X]]));
return 0;
}