洛谷P3321 [SDOI2015]序列统计（NTT）

题意：$a_i\in S$，求$\prod_{i=1}^na_i\equiv x\pmod{m}$的方案数

这题目太珂怕了……数学渣渣有点害怕……kelin大佬TQL

设$f[i][j]$表示$\prod_{k=1}^ia_k\equiv j\pmod{m}$的方案数

那么$$f[2*i][j]=\sum_{ab\equiv j\pmod{m}}f[i][a]f[i][b]$$

然后因为$m$是质数。质数有一个叫做原根的东西，质数$p$的原根$g$满足$g^i\ mod\ p$在$i$为$[1,p-1]$时互不相同，然后根据费马小定理$g^{p-1}\equiv 1\pmod{p}$，所以$i$在$[0,p-2]$的范围内$g^{i}$能取遍[1,p-1]的所有数（因为原根一般都特别小，所以可以直接暴力求，这个可以看代码）

因为$g^A\equiv a\pmod{m}$，每一个$A$和$a$互相对应，那么我们可以用$A$来代替$a$

则上式变为$$f[2*i][K]\equiv \sum_{g^Ag^B\equiv g^K\pmod{m}}f[i][A]f[i][B]$$

$$f[2*i][K]\equiv \sum_{g^{A+B}\equiv g^K\pmod{m}}f[i][A]f[i][B]$$

根据费马小定理$a^b\equiv a^{b\ mod\ p-1}\pmod{p}$，可得$$f[2*i][K]\equiv \sum_{g^{(A+B)\ mod\ m-1}=g^K}f[i][A]f[i][B]$$

$$f[2*i][K]\equiv \sum_{A+B\equiv K\pmod{m-1}}f[i][A]f[i][B]$$

设$g[K]=\sum_{A+B=K}f[i][A]f[i][B]$，则$$f[i*2][K]=g[K]+g[K+m-1]$$

然后这个每一层的转移都是一样的，所以用多项式快速幂来计算

 //minamoto

 #include<iostream>

 #include<cstdio>

 #include<algorithm>

 #define ll long long

 #define swap(x,y) (x^=y,y^=x,x^=y)

 #define mul(x,y) (1ll*x*y%P)

 #define add(x,y) (x+y>=P?x+y-P:x+y)

 #define dec(x,y) (x-y<0?x-y+P:x-y)

 using namespace std;

 #define getc() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++)

 char buf[<<],*p1=buf,*p2=buf;

 inline int read(){

     #define num ch-'0'

     char ch;bool flag=;int res;

     while(!isdigit(ch=getc()))

     (ch=='-')&&(flag=true);

     for(res=num;isdigit(ch=getc());res=res*+num);

     (flag)&&(res=-res);

     #undef num

     return res;

 }

 const int N=,P=;

 int n,m,vis[N],F[N],G[N],A[N],B[N],O[N];

 int l,limit=,r[N],x,S,pr;

 inline int ksm(int a,int b,int P){

     int res=;a%=P;

     while(b){

         if(b&) res=mul(res,a);

         a=mul(a,a),b>>=;

     }

     return res;

 }

 inline int calc(int x){

     //求原根，若只有j=x-1时i^j=1(mod x)，i是x的原根

     if(x==) return ;

     for(int i=;;++i){

         bool flag=;

         for(int j=;j*j<x;++j)

         if(ksm(i,(x-)/j,x)==){flag=false;break;}

         if(flag) return i;

     }

 }

 void NTT(int *A,int type){

     for(int i=;i<limit;++i)

     if(i<r[i]) swap(A[i],A[r[i]]);

     for(int mid=;mid<limit;mid<<=){

         int R=mid<<,Wn=ksm(,(P-)/R,P);O[]=;

         for(int j=;j<mid;++j) O[j]=mul(O[j-],Wn);

         for(int j=;j<limit;j+=R){

             for(int k=;k<mid;++k){

                 int x=A[j+k],y=mul(O[k],A[j+k+mid]);

                 A[j+k]=add(x,y),A[j+k+mid]=dec(x,y);

             }

         }

     }

     if(type==-){

         reverse(A+,A+limit);

         for(int i=,inv=ksm(limit,P-,P);i<limit;++i)

         A[i]=mul(A[i],inv);

     }

 }

 void Mul(int *G,int *F){

     for(int i=;i<limit;++i) A[i]=G[i],B[i]=F[i];

     NTT(A,),NTT(B,);

     for(int i=;i<limit;++i) A[i]=mul(A[i],B[i]);

     NTT(A,-);

     for(int i=;i<m-;++i) G[i]=add(A[i],A[i+m-]);

 }

 void solve(int b){

     G[]=;

     while(b){

         if(b&) Mul(G,F);

         b>>=,Mul(F,F);

     }

 }

 int main(){

 //    freopen("testdata.in","r",stdin);

     n=read(),m=read(),x=read(),S=read();

     pr=calc(m);

     for(int i=,v;i<=S;++i)

     vis[v=read()]=;

     int pos=-;

     for(int i=,j=;i<m-;++i,j=j*pr%m){

         if(vis[j]) F[i]=;

         if(j==x) pos=i;

     }

     if(pos==-) return puts(""),;

     while(limit<=((m-)<<)) limit<<=,++l;

     for(int i=;i<limit;++i)

     r[i]=(r[i>>]>>)|((i&)<<(l-));

     solve(n);

     printf("%d\n",G[pos]%P);

     return ;

 }

巴特西

洛谷P3321 [SDOI2015]序列统计（NTT）

最新文章

热门文章