题目描述
小C有一个集合S，里面的元素都是小于M的非负整数。他用程序编写了一个数列生成器，可以生成一个长度为N的数列，数列中的每个数都属于集合S。小C用这个生成器生成了许多这样的数列。但是小C有一个问题需要你的帮助：给定整数x，求所有可以生成出的，且满足数列中所有数的乘积mod M的值等于x的不同的数列的有多少个。小C认为，两个数列{Ai}和{Bi}不同，当且仅当至少存在一个整数i，满足Ai≠Bi。另外，小C认为这个问题的答案可能很大，因此他只需要你帮助他求出答案mod 1004535809的值就可以了。
题解
先考虑一个dp，就是设dp[i][j]表示已经构造好了前i个元素，它们的乘积为j的方案数。
转移：dp[i][j]=dp[i-1][k]*f[j/k]
看起来很像是卷积然鹅不是，他们中间是乘法关系而不是加法。
这时我们考虑一个限制，就是m是一个质数。
它有什么好处，就是当x,y互质时，那么x1x2....xy-1会遍历0-y-1的所有数。、
这样我们可以把1-m-1代换一下。
dp[i][j]=dp[i-1][k]*f[l] (gkgl=gj)
因为存在一一对应的关系，所以我们就可以代换了。
然后就变成了卷积的形式，多项式快速幂解决，因为每层的转移都是一样的。
代码
#include<iostream> #include<cstdio> #include<cstring> #define N 32002 using namespace std; typedef long long ll; const int mod=1004535809; const int G=3; const int Gi=334845270; ll l,ny2,x,rev[N],L,n,m,a[N],b[N],s,g,c[N],tran[N],f[N]; inline int rd(){ int x=0;char c=getchar();bool f=0; while(!isdigit(c)){if(c=='-')f=1;c=getchar();} while(isdigit(c)){x=(x<<1)+(x<<3)+(c^48);c=getchar();} return f?-x:x; } inline ll power(ll x,ll y){ ll ans=1; while(y){if(y&1)ans=ans*x%mod;x=x*x%mod;y>>=1;} return ans; } inline void NTT(ll *a,int tag){ for(int i=0;i<l;++i)if(i>rev[i])swap(a[i],a[rev[i]]); for(int i=1;i<l;i<<=1){ ll wn=power(tag==1?G:Gi,(mod-1)/(i<<1)); for(int j=0;j<l;j+=(i<<1)){ ll w=1; for(int k=0;k<i;++k,w=w*wn%mod){ int x=a[j+k],y=a[i+j+k]*w%mod; a[j+k]=(x+y)%mod;a[i+j+k]=(x-y+mod)%mod; } } } } inline void ch(ll a[],ll *b){ memcpy(c,a,sizeof(c)); NTT(c,1);NTT(b,1); for(int i=0;i<l;++i)b[i]=b[i]*c[i]%mod; NTT(b,-1); for(int i=0;i<l;++i)b[i]=b[i]*ny2%mod; for(int i=m;i<(m<<1);++i)(b[i-m]+=b[i])%=mod,b[i]=0; } inline ll ksm(ll x,ll y,ll m){ ll ans=1; while(y){if(y&1)ans=ans*x%m;x=x*x%m;y>>=1;} return ans; } inline int get_g(int m){ for(int i=2;i<=m-2;++i)if((m-1)%i==0)f[++f[0]]=i; for(int i=2;;++i){ bool x=1; for(int j=1;j<=f[0]&&x;++j)if(ksm(i,f[j],m)==1)x=0; if(x)return i; } } int main(){ n=rd();m=rd();x=rd();s=rd(); g=get_g(m); for(ll i=0,k=1;i<m-1;++i,k=k*g%m)tran[k]=i; m--; l=1;L=0; while(l<(m<<1))l<<=1,L++;int y; ny2=power(l,mod-2); for(int i=0;i<l;++i)rev[i]=(rev[i>>1]>>1)|((i&1)<<(L-1)); for(int i=1;i<=s;++i){ y=rd(); if(y)a[tran[y]]=1; } b[tran[1]]=1; while(n){ if(n&1)ch(a,b); ch(a,a);n>>=1; } cout<<b[tran[x]]; return 0; }
原根的求法：
暴力枚举，然后枚举m-1的所有质因子，若i^p==1则不是原根。
inline int get_g(int m){ for(int i=2;i<=m-2;++i)if((m-1)%i==0)f[++f[0]]=i; for(int i=2;;++i){ bool x=1; for(int j=1;j<=f[0]&&x;++j)if(ksm(i,f[j],m)==1)x=0; if(x)return i; } }