bzoj3992【SDOI2015】序列统计

3992: [SDOI2015]序列统计

Time Limit: 30 Sec Memory Limit: 128 MB

Submit: 673 Solved: 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 2

1 2

Sample Output

HINT

【例子说明】

能够生成的满足要求的不同的数列有(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

Round 1 感谢yts1999上传

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<iostream>

#include<cstdio>

#include<cstring>

#include<cstdlib>

#include<cmath>

#include<algorithm>

#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<<bit)-1) if (rev[i]>i) swap(a[i],a[rev[i]]);

	F(i,1,bit)

	{

		int y=(1ll*flag*(mod-1)/(1<<i)+mod-1)%(mod-1);

		ll wn=power(g,y,mod);

		for(int j=0;(j<1<<bit);j+=(1<<i))

		{

			ll w=1;

			F(k,j,j+(1<<(i-1))-1)

			{

				int u=a[k],v=w*a[k+(1<<(i-1))]%mod;

				a[k]=(u+v)%mod;

				a[k+(1<<(i-1))]=((u-v)%mod+mod)%mod;

				w=w*wn%mod;

			}

		}

	}

	if (flag<0) F(i,0,(1<<bit)-1) a[i]=1ll*a[i]*inv%mod;

}

inline void convol(int *a,int *b)

{

	int len=1<<bit;

	F(i,0,len-1) c[i]=b[i];

	ntt(a,1);ntt(c,1);

	F(i,0,len-1) a[i]=(ll)a[i]*c[i]%mod;

	ntt(a,-1);

	for(int i=m-1,j=0;i<len;i++,j++) a[j]=(a[j]+a[i])%mod,a[i]=0;

}

int main()

{

	n=read();m=read();num=read();s=read();

	F(i,1,s) a[i]=read();

	mg=get_primitive_root(m);

	g=get_primitive_root(mod);

	int tmp=1;

	F(i,0,m-2){ind[tmp]=i;tmp=tmp*mg%m;}

	for(bit=0;(1<<bit)<(m-1)*2;bit++);

	inv=power(1<<bit,mod-2,mod);

	F(i,0,(1<<bit)-1) rev[i]=rev[i>>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;

}

巴特西