首页 > 代码库 > BZOJ 3992: [SDOI2015]序列统计 [快速数论变换 生成函数 离散对数]
BZOJ 3992: [SDOI2015]序列统计 [快速数论变换 生成函数 离散对数]
3992: [SDOI2015]序列统计
Time Limit: 30 Sec Memory Limit: 128 MBSubmit: 1017 Solved: 466
[Submit][Status][Discuss]
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的值。
对于全部的数据，1<=N<=109，3<=M<=8000，M为质数，1<=x<=M-1，输入数据保证集合S中元素不重复
题意：有多少长为n的序列序列中每个元素属于S且乘积mod M=x
这道题太强啦
首先，发现m是一个质数，我们可以把乘法简化成加法
m的原根为g，让Si中元素取以g为底对模m的离散对数，记为ind[i]
因为g0,1,...,m-1 (mod m) 互不相同，所以可以把[1,m-1]的数字表示出来，并且它的取值为[0,m-2]
离散对数也满足一些类似对数的性质，如ind(ab)=ind(a)+ind(b) (mod m-1) 证明的话我从网上随便找了个课件
然后乘法就变成加法啦！
变成加法是为了用生成函数
这是一个可重集的组合问题，我们构造一个生成函数A(x) a[ind[si]]=1，这样如果选择si次数就会加上ind[si]
AN的ind[x]项系数就是答案啦
如何计算呢？
因为这是模意义下的乘法，所以要用NNT
然后注意要求的是ind[si]加起来mod(m-1) = ind[x]，所以乘法结束时需要把>m-1的加到mod (m-1) 上并清零
然后用多项式快速幂，单位元就是a[0]=1
注意别把语句放错位置以及别传错参数......
#include <iostream>#include <cstdio>#include <string>#include <algorithm>#include <cmath>using namespace std;typedef long long ll;const int N=1e5+5;inline int read(){ char c=getchar();int x=0,f=1; while(c<‘0‘||c>‘9‘){if(c==‘-‘)f=-1;c=getchar();} while(c>=‘0‘&&c<=‘9‘){x=x*10+c-‘0‘;c=getchar();} return x*f;}int n,m,x,S;ll A[N],ans[N]; ll P=1004535809,MOD=P;ll Pow(ll a,ll b,ll MOD){ ll ans=1; for(;b;b>>=1,a=a*a%MOD) if(b&1) ans=ans*a%MOD; return ans;}ll PrimitiveRoot(ll p){ if(p==2) return 1; for(ll g=2;g<p;g++){ bool flag=1;ll m=sqrt(p); for(ll i=2;i<=m;i++) if((p-1)%i==0) if(Pow(g,(p-1)/i,p)==1) {flag=0;break;} if(flag) return g; } return 0;}int ind[N];void iniInd(){ int g=PrimitiveRoot(m),a=1; for(int i=0;i<m-1;i++,a=a*g%m) ind[a]=i;} struct NumberTheoreticTransform{ int n,rev[N]; ll g; void ini(int m){ n=1; while(n<m) n<<=1; int k=0; while((1<<k)<n) k++; for(int i=0;i<n;i++){ int t=0; for(int j=0;j<k;j++) if(i&(1<<j)) t|=(1<<(k-j-1)); rev[i]=t; } g=3; } void DFT(ll *a,int flag){ for(int i=0;i<n;i++) if(i<rev[i]) swap(a[i],a[rev[i]]); for(int l=2;l<=n;l<<=1){ int m=l>>1; ll wn=Pow(g,flag==1?(P-1)/l:P-1-(P-1)/l,P); for(ll *p=a;p!=a+n;p+=l){ ll w=1; for(int k=0;k<m;k++){ ll t=w*p[k+m]%P; p[k+m]=(p[k]-t+P)%P; p[k]=(p[k]+t)%P; w=w*wn%P; } } } if(flag==-1){ ll inv=Pow(n,P-2,P);; for(int i=0;i<n;i++) a[i]=a[i]*inv%P; } } void SQR(ll *A){ DFT(A,1); for(int i=0;i<n;i++) A[i]=A[i]*A[i]%MOD; DFT(A,-1); for(int i=0;i<=m-2;i++) A[i]=(A[i]+A[i+m-1])%MOD,A[i+m-1]=0; } ll C[N]; void MUL(ll *A,ll *B){ for(int i=0;i<n;i++) C[i]=B[i]; DFT(A,1);DFT(C,1); for(int i=0;i<n;i++) A[i]=A[i]*C[i]%MOD; DFT(A,-1); for(int i=0;i<=m-2;i++) A[i]=(A[i]+A[i+m-1])%MOD,A[i+m-1]=0; } void PowPoly(ll *A,int b,ll *ans){ ans[0]=1; for(;b;b>>=1,SQR(A)) if(b&1) MUL(ans,A); }}fft; int main(){ freopen("in","r",stdin); n=read();m=read();x=read();S=read(); fft.ini(m+m); iniInd(); for(int i=1;i<=S;i++){ int x=read(); if(x) A[ind[x]]=1; } fft.PowPoly(A,n,ans); printf("%lld",ans[ind[x]]);}
BZOJ 3992: [SDOI2015]序列统计 [快速数论变换 生成函数 离散对数]
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。