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是逆元

这个复杂度显然不科学
我们先放下这个问题，看一种新的算法：

诶诶诶
这个模数怎么这么熟悉
1004535809
那这道题我们要是能找到卷积的形式
就可以套NTT板子了

归根到底
g^(p-1)同余于1（mod p）
则称g是p的原根

求原根目前的做法只能是从2开始枚举，
然后暴力判断g^(p-1)同余于1 (mod p)
是否当且仅当指数为p-1的时候成立
而由于原根一般都不大，所以可以暴力得到

当然一些常见的模数是要记住的
像这道题中，1004535809就是一个原根为3的经典模数

找到了学姐的blog，讲的蛮不错
http://blog.****.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;
}