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中元素不重复
分析：
先报算法：NTT
这种东西的思路都是
找多项式，看出是卷积形式，然后套板子
好像做过一道很像的题呢
那道题是叫你统计n个数相加，模数一定的方案数
那我们第一件事就是想dp啊
f[i][j]=sigma f[i-1][j*inv[k]] //inv是逆元
这个复杂度显然不科学
我们先放下这个问题，看一种新的算法：
FNT/NTT
诶诶诶
这个模数怎么这么熟悉
1004535809
那这道题我们要是能找到卷积的形式
就可以套NTT板子了
归根到底
g^(p-1)同余于1（mod p）
则称g是p的原根
求原根目前的做法只能是从2开始枚举，
然后暴力判断g^(p-1)同余于1 (mod p)
是否当且仅当指数为p-1的时候成立
而由于原根一般都不大，所以可以暴力得到
当然一些常见的模数是要记住的
像这道题中，1004535809就是一个原根为3的经典模数
找到了学姐的blog，讲的蛮不错
http://blog.csdn.net/clover_hxy/article/details/56495911
我在这里说一下自己的理解：
原根的次方可以表示p以内的任意数字，因为是模意义下的运算
我们当然可以用原根的任意次幂表示任意数字（mod p）
这样我们可以把之前的乘法变成一个加法
新的状态就变成了
f[i][j]表示选到第i个数，结果是g^j的方案数
f[i][j+k]+=f[i-1][j] //同底数幂相乘，底数不变，指数相加
用h[i]表示原根的i次幂的方案数，q[i]表示原根的i次幂是否在集合中
h[i]=sigma h[j]*q[i-j]
这就是一个卷积的形式了
tip
主程序中是正常的预处理
fn很容易带成n
原根的求法觉得很值得记下：
为了快速处理
我们用了一个类似于快速幂的东西
mul的过程和FFT很像，唯一需要注意的是，最后在/fn的时候
要处理出一个逆元，化除为乘
NTT的过程和FFT基本一样
这是分割线———————————————————————————————-
查了半天错，才发现是自己定义的一个swap函数
没有带取地址符。。。orz
在NTT函数中，变量名老是搞错，
现在才明白执行语句顺序的重要性
以前写FFT的时候，
a[m+j+k]的操作总是在a[j+k]之前，我也没怎么注意
结果这次顺序写反，就jj了
没有好好读题
题目是让在S中选择n个数，S中每个数的大小都不超过m，个数是tot
在传参进入slove的时候，应该传n，QAQ
那么卷机过后的数组长度就是2*（m-1）
WA.st
快速幂少%了一下
求原根的时候KSM(i,(x-1)/j,x)
WA.nd
lld<–I64d
总觉得这道题真的是很艰难的A了
这里写代码片
#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#define ll long long
using namespace std;
const int N=17000;
const ll mod=1004535809;
int n,m,X,tot,yg,M,fn,R[N];
bool vis[N];
ll h[N],a[N],b[N],q[N];
ll KSM(ll a,ll b,ll p)
{
a%=p;
ll t=1;
while (b)
{
if (b&1)
t=(t*a)%p;
a=(a*a)%p;
b>>=1;
}
return t%p;
}
int calc(int x) //求原根
{
if (x==2) return 1;
for (int i=2;i;i++)
{
bool pp=1;
for (int j=2;j*j<x;j++)
if (KSM(i,(x-1)/j,x)==1)
//只要有一个非mod-1的数幂也同余于1，就不合法
{
pp=0;
break;
}
if (pp) return i;
}
}
void NTT(ll *a,int n,int opt)
{
int i,j=0,k;
for (i=0;i<n;i++)
{
if (i>j) swap(a[i],a[j]);
for (int l=n>>1;(j^=l)<l;l>>=1);
}
for (i=1;i<n;i<<=1)
{
ll wn=KSM(3,(mod-1)/(i<<1),mod); //1004535809原根
int m=i<<1;
for (j=0;j<n;j+=m)
{
ll w=1;
for (k=0;k<i;k++,w=(w*wn)%mod)
{
ll z=(w*a[j+k+i])%mod;
a[j+k+i]=(a[j+k]-z+mod)%mod;
a[j+k]=(a[j+k]+z)%mod;
}
}
}
if (opt==-1) reverse(a+1,a+n);
}
void mul(ll h[N],ll q[N])
{
for (int i=0;i<fn;i++) a[i]=h[i]%mod;
for (int i=0;i<fn;i++) b[i]=q[i]%mod;
NTT(a,fn,1); NTT(b,fn,1);
for (int i=0;i<fn;i++) a[i]=(a[i]*b[i])%mod;
NTT(a,fn,-1);
ll inv=KSM(fn,mod-2,mod); //逆元
for (int i=0;i<fn;i++) a[i]=(a[i]*inv)%mod;
//因为是模意义下的整数除法，就不能像FFT一样这么耿直的直接/了
for (int i=0;i<m-1;i++)
h[i]=(a[i]+a[i+m-1])%mod;
}
void solve(int x)
{
h[0]=1;
while (x) //类似一个快速幂，快速处理卷积
{
if (x&1) mul(h,q);
x>>=1;
mul(q,q);
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&X,&tot);
yg=calc(m);
for (int i=1;i<=tot;i++)
{
int x;
scanf("%d",&x);vis[x]=1;
}
int pos=-1;
for (int i=0,j=1;i<m-1;i++,j=(j*yg)%m)
{
if (vis[j]) q[i]=1; //原根的i次幂在不在集合中
if (j==X) pos=i; //答案是yg的pos次幂
}
M=(m-1)*2; fn=1;
while (fn<=M) fn<<=1;
solve(n);
if (pos!=-1) printf("%lld
",h[pos]%mod);
else printf("0
");
return 0;
}