Description

小C有一个集合\(S\)，里面的元素都是小于\(M\)的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为\(N\)的数列，数列中的每个数都属于集合\(S\)。小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：

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

Solution

仍然是用生成函数来做，但是，并不能实现下标乘的卷积

发现条件中给出\(M\)一定是个质数，看到质数就想到原根，把每个数都用原根的幂来表示，化乘为加

\(M \leq 8000\)，它的原根直接暴力求就可以了

剩下的就是\(NTT\)优化多项式快速幂了

Code 

#include
    
     #define ll long long#define max(a,b) ((a)>(b)?(a):(b))#define min(a,b) ((a)<(b)?(a):(b))inline int read(){    int x=0,f=1;char ch=getchar();    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}    while(ch>='0'&&ch<='9'){x=(x<<3)+(x<<1)+ch-'0';ch=getchar();}    return x*f;}#define mod 1004535809#define g 3#define invg 334845270#define MN 8005inline int fpow(int x,int m,int p=mod){    register int ret=1;    for(;m;x=1ll*x*x%p,m>>=1)if(m&1)ret=1ll*ret*x%p;    return ret;}int ct,fac[MN];inline int getg(int p){    register int i,j;ct=0;    for(i=2;i<=p-2;++i) if((p-1)%i==0) fac[++ct]=i;    for(i=2;;++i)    {        register bool yes=true;        for(j=1;j<=ct;++j) if(fpow(i,fac[j],p)==1) {yes=false;break;}        if(yes) return i;     }}int G,mi[MN],s[MN<<2],t[MN<<2],N,di,pos[MN<<2],invN,M;inline void NTT(int *a,int type){    register int i,j,p,k;    for(i=0;i
     
      
       0?g:invg,(mod-1)/(i<<1));        for(p=i<<1,j=0;j
       
        =M-1;--i) (a[i-M+1]+=a[i])%=mod,a[i]=0;}inline void pro(int *a,int *b){    register int i;    NTT(a,1);NTT(b,1);for(i=0;i
        
         =M-1;--i) (a[i-M+1]+=a[i])%=mod,a[i]=0;}inline void pow(int *a,int m){    register int i;    for(N=1;N<=M+M-2;N<<=1,di++);    invN=fpow(N,mod-2);    for(i=0;i
         
          >1]>>1)|((i&1)<<(di-1)); for(t[0]=1;m;self(a),m>>=1) if(m&1) pro(t,a);}int main(){ register int i,n,x,S,tmp; n=read();M=read();x=read();S=read();G=getg(M); for(i=tmp=1;i
         
        
       
      
     
    

---

Blog来自PaperCloud，未经允许，请勿转载，TKS！