数论劲啊

原题：

小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。

小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为，两个数列{Ai}和{Bi}不同，当且仅当至少存在一个整数i，满足Ai≠Bi。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案mod 1004535809的值就可以了。

1<=N<=10^9，3<=M<=8000，M为质数，0<=x<=M-1，输入数据保证集合S中元素不重复

 

首先因为M是质数并且0<=x和S中的元素<=M-1，就说明M有原根而且能很快求出来

于是对于i∈[0,M-1]的数都可以表示成原根的ki(k∈[0,M-1])次幂形式而且k互补相同

于是乘法就转化成了幂的加法，问题变成给|S|个数，求选n个数使得这n个数的和膜M==x的方案数（一个数可以选多次

所以生成函数，对于每个集合中的数si的ki，用ai表示kj==i有多少个（实际上最多只有一个，因为ki互不相同，同时S中的数互不相同

那么最终生成的多项式就是A=a_0+a_1*x+a_2*x^2+……a_{m-1}*x^{m-1}

因为有n个物品，所以多项式卷积n次

因为给的模数是恩梯梯模数，所以使用NTT计算精确答案

最后的答案就是(A^n)的第k_{x}相

代码：

1 #include
      
        2 #include
       
         3 #include
        
          4 #include
         
           5 #include
          
            6 using namespace std; 7 #define ll long long 8 const ll mo=1004535809; 9 int rd(){
    int z=0,mk=1;  char ch=getchar();10     while(ch<'0'||ch>'9'){
    if(ch=='-')mk=-1;  ch=getchar();}11     while(ch>='0'&&ch<='9'){z=(z<<3)+(z<<1)+ch-'0';  ch=getchar();}12     return z*mk;13 }14 int wtp=0,wtc[32];15 void wt(int x,char y){16     if(!x){  putchar('0');  return ;}17     if(x<0)  putchar('-'),x=-x;18     while(x)  wtc[++wtp]=x%10+'0',x/=10;19     while(wtp)  putchar(wtc[wtp--]);20     putchar(y);21 }22 ll n,m,t,s;  int g,tg[210000];23 ll a[210000],b[210000],tmp[210000],_x,_y;24 int rvs[210000],dg[32],N,L;  ll _1_N;25 int stck[210000],tp=0;26 ll qcp(ll x,int y,int p){27     ll z=1,bs=x;28     for(;y;y>>=1){29         if(y&1)  z=(z*bs)%p;30         bs=(bs*bs)%p;31     }32     return z;33 }34 int gtg(){35     int _m=m-1;36     for(int i=2;i<=_m;++i)if(!(_m%i)){37         stck[++tp]=i;38         while(!(_m%i))  _m/=i;39     }40     for(int i=2,mk=false;;++i,mk=false){41         for(int j=1;j<=tp;++j)42             if(qcp(i,(m-1)/stck[j],m)==1){43                 mk=true;44                 break;45             }46         if(!mk)  return i;47     }48 }49 void ntt(ll x[],ll mk){50     for(int i=0;i
           
            >1);++j){57 _x=x[j],_y=(x[j+(i>>1)]*w)%mo;58 x[j]=(_x+_y)%mo,x[j+(i>>1)]=(_x-_y+mo)%mo;59 w=(w*wn)%mo;60 }61 }62 }63 if(mk==mo-2) for(int i=0;i
            
             >=1){68 ntt(a,1);69 if(n&1){70 ntt(b,1); for(int i=0;i
             
              =m-1;--i) b[i-m+1]=(b[i-m+1]+b[i])%mo,b[i]=0;72 }73 for(int i=0;i
              
               =m-1;--i) a[i-m+1]=(a[i-m+1]+a[i])%mo,a[i]=0;76 }77 }78 int main(){ //freopen("ddd.in","r",stdin);79 cin>>n>>m>>t>>s;80 g=gtg();81 for(int i=0,x=1;i
               
                >=1,++k) dg[k]=j&1;91 for(int j=0;j