bzoj3992【SDOI2015】序列统计
程序员文章站
2022-09-15 19:42:20
3992: [SDOI2015]序列统计
Time Limit:30 SecMemory Limit:128 MB
Submit:673Solved:327
[S...
3992: [SDOI2015]序列统计
Time Limit:30 SecMemory Limit:128 MBSubmit:673Solved:327
[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的值。
Sample Input
4 3 1 21 2
Sample Output
8HINT
【样例说明】
可以生成的满足要求的不同的数列有(1,1,1,1)、(1,1,2,2)、(1,2,1,2)、(1,2,2,1)、(2,1,1,2)、(2,1,2,1)、(2,2,1,1)、(2,2,2,2)。
【数据规模和约定】
对于10%的数据,1<=N<=1000;
对于30%的数据,3<=M<=100;
对于60%的数据,3<=M<=800;
对于全部的数据,1<=N<=109,3<=M<=8000,M为质数,1<=x<=M-1,输入数据保证集合S中元素不重复
Source
NTT第一题
首先可以发现1004535809=479*2^21+1,而且是一个质数,所以可以用NTT解决。
用f[i][j]表示i个数模m等于g^j的方案数(i为2的整数次幂,g为m的原根),则f[i][j]=∑f[i/2][k]*f[i/2][j-k]。这样就成了卷积形式,NTT搞定。但n并不一定是2的整数次幂,这里就要用到快速幂的思想(详见代码)。
#include #include #include #include #include #include #define F(i,j,n) for(int i=j;i<=n;i++) #define D(i,j,n) for(int i=j;i>=n;i--) #define ll long long #define maxn 40000 #define mod 1004535809 using namespace std; int n,m,num,s,mg,g,bit,inv; int a[maxn],c[maxn],A[maxn],B[maxn],ind[maxn],rev[maxn]; 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*10+ch-'0';ch=getchar();} return x*f; } inline ll power(ll x,int y,int p) { ll ret=1; for(;y;y>>=1,x=x*x%p) if (y&1) ret=ret*x%p; return ret; } inline bool get_order(int x,int m) { int lim=sqrt(m),phi=m-1; F(i,1,lim) if (phi%i==0) { if (power(x,i,m)==1){if (i!=m-1) return false;} if (power(x,phi/i,m)==1){if (phi/i!=m-1) return false;} } return true; } inline int get_primitive_root(int x) { F(i,2,x) if (get_order(i,x)) return i; } inline void ntt(int *a,int flag) { F(i,0,(1<i) swap(a[i],a[rev[i]]); F(i,1,bit) { int y=(1ll*flag*(mod-1)/(1<>1]>>1|((i&1)<<(bit-1)); A[0]=1; F(i,1,s) if (a[i]) B[ind[a[i]]]=1; for(;n;convol(B,B),n>>=1) if (n&1) convol(A,B); printf("%d\n",A[ind[num]]); return 0; }