BZOJ 3992 【SDOI2015】 序列统计

题目链接：序列统计

　　我来复习板子了……这道题也是我写的第一发求原根啊？

　　求原根方法：

　　从小到大依次枚举原根。设当前枚举的原根为\(x\)，模数为\(p\)，\(p-1\)的质因数分别为\(p_1,p_2,\dots,p_m\)，则只需检验\(x^{\frac{p-1}{p_i}}\equiv1 \pmod{p}\)是否成立即可。如果成立则\(x\)不是原根。

　　然后这道题朴素\(dp\)就不讲了。设\(m\)的原根为\(g\)，那么把每个数表示成\(g^k\)的形式就可以乘法变加法了，就成为了\(NTT\)板子题，快速幂一下就做完了。注意这道题是循环卷积，记得把多出来的那部分弄到前面去。

　　下面贴代码：

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cmath>

#include<complex>

#define File(s) freopen(s".in","r",stdin),freopen(s".out","w",stdout)

#define maxn 100010

#define mod 1004535809

using namespace std;

typedef long long llg;

int R[maxn],n,m,N,L,T,rt,pm;

int a[maxn],b[maxn],c[maxn];

bool vis[maxn];

int getint(){

	int w=0;bool q=0;

	char c=getchar();

	while((c>'9'||c<'0')&&c!='-') c=getchar();

	if(c=='-') c=getchar(),q=1;

	while(c>='0'&&c<='9') w=w*10+c-'0',c=getchar();

	return q?-w:w;

}

int qpow(int x,int y,int c){

	int s=1;

	while(y){

		if(y&1) s=1ll*s*x%c;

		x=1ll*x*x%c; y>>=1;

	}

	return s;

}

void root(int p){

	if(p==2){rt=1;return;}

	for(rt=2;;rt++){

		bool w=1; int x=p-1;

		for(int i=2;i*i<=x;i++)

			if(x%i==0){

				if(qpow(rt,(p-1)/i,p)==1){w=0;break;}

				while(x%i==0) x/=i;

			}

		if(x!=1 && qpow(rt,(p-1)/x,p)==1) w=0;

		if(w) break;

	}

}

void DFT(int *a){

	for(int i=0;i<n;i++) if(i<R[i]) swap(a[i],a[R[i]]);

	for(int i=1;i<n;i<<=1){

		int gn=qpow(3,(mod-1)/(i<<1),mod),x,y;

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

			int g=1;

			for(int k=0;k<i;k++,g=1ll*g*gn%mod){

				x=a[j+k]; y=1ll*g*a[j+i+k]%mod;

				a[j+k]=x+y; if(a[j+k]>=mod) a[j+k]-=mod;

				a[j+i+k]=x-y; if(x<y) a[j+i+k]+=mod;

			}

		}

	}

}

void NTT(int *a,int *c){

	for(int i=0;i<n;i++) b[i]=c[i]; DFT(a);

	if(a!=c) DFT(b);

	else for(int i=0;i<n;i++) b[i]=a[i];

	for(int i=0;i<n;i++) a[i]=1ll*a[i]*b[i]%mod;

	DFT(a); reverse(a+1,a+n);

	for(int i=0;i<n;i++) a[i]=1ll*a[i]*N%mod;

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

}

int main(){

	File("a");

	T=getint()-1; n=m=getint()-1;

	int X,siz; pm=m; root(++pm);

	X=getint(),siz=getint(); while(siz--) vis[getint()]=1;

	for(int p=1,i=0;i<pm-1;i++,p=p*rt%pm)

		if(vis[p]) a[i]=c[i]=1;

	m+=n-1; for(n=1;n<m;n<<=1) L++; N=qpow(n,mod-2,mod);

	for(int i=0;i<n;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));

	while(T){

		if(T&1) NTT(a,c);

		NTT(c,c); T>>=1;

	}

	for(int p=1,i=0;i<pm-1;i++,p=p*rt%pm)

		if(p==X) printf("%d",a[i]);

	return 0;

}