记录编号	298531	评测结果	AAAAAAAAAA
题目名称	[SDOI 2015] 序列统计	最终得分	100
用户昵称	TenderRun	是否通过	通过
代码语言	C++	运行时间	10.340 s
提交时间	2016-08-21 23:18:30	内存使用	0.65 MiB

#include <iostream>
#include <cstring>
#include <cstdio>
using namespace std;
const int N=32768,G=3;
const int MOD=1004535809;
int g,n,m,x,s,pos[N],num[N];
int Qpow(int x,int k,int mod){
	long long ret=1;
	while(k){
		if(k&1)ret=1ll*ret*x%mod;
		x=1ll*x*x%mod;k>>=1;
	}
	return ret;
}

void Rader(int *a,int len){
	for(int i=1,j=len>>1;i<len-1;i++){
		if(i<j)swap(a[i],a[j]);
		int k=len>>1;
		while(j>=k){
			j-=k;
			k>>=1;
		}
		j+=k;
	}
}

void NTT(int *a,int len,int on){
	Rader(a,len);
	for(int h=2,wn;h<=len;h<<=1){
		if(on==1)wn=Qpow(G,(MOD-1)/h,MOD);
		else wn=Qpow(G,MOD-1-(MOD-1)/h,MOD);
		for(int j=0;j<len;j+=h){
			int w=1,x,y;
			for(int k=j;k<j+(h>>1);k++){
				x=a[k];y=1ll*a[k+(h>>1)]*w%MOD;
				a[k]=(x+y)%MOD;a[k+(h>>1)]=(x-y+MOD)%MOD;
				w=1ll*w*wn%MOD;
			}
		}
	}
	if(on==-1){
		int inv=Qpow(len,MOD-2,MOD);
		for(int i=0;i<len;i++)
			a[i]=1ll*a[i]*inv%MOD;
	}	
}

int f[N],r[N],l=N/2;
void Solve(){
	for(int i=0;i<N;i++)
		r[i]=f[i];n-=1;
	while(n){
		NTT(f,N,1);
		if(n&1){
			NTT(r,N,1);
			for(int i=0;i<N;i++)r[i]=1ll*r[i]*f[i]%MOD;
			NTT(r,N,-1);
			for(int i=m-1;i<N;i++)(r[i%(m-1)]+=r[i])%=MOD,r[i]=0;
		}
		for(int i=0;i<N;i++)f[i]=1ll*f[i]*f[i]%MOD;
		NTT(f,N,-1);
		for(int i=m-1;i<N;i++)(f[i%(m-1)]+=f[i])%=MOD,f[i]=0;
		n>>=1;
	}
	printf("%d\n",r[pos[x]]);
}

void Solve_Zero(){int cnt=0,ans;
	for(int i=1;i<=s;i++)if(!num[i])cnt++;
	ans=Qpow(s,n,MOD)-Qpow(s-cnt,n,MOD);
	printf("%d\n",ans);
}
int main(){
	freopen("sdoi2015_sequence.in","r",stdin);
	freopen("sdoi2015_sequence.out","w",stdout);
	scanf("%d%d%d%d",&n,&m,&x,&s);
	for(int i=1;i<=s;i++)
		scanf("%d",&num[i]);
	if(!x)Solve_Zero();
	for(g=1;g<m;g++){int i;
		for(i=1;i<m-1;i++)
			if(Qpow(g,i,m)==1)
				break;
		if(i==m-1&&Qpow(g,m-1,m)==1)break;		
	}
	for(int i=1;i<m;i++)
		pos[Qpow(g,i,m)]=i%(m-1);
	for(int i=1;i<=s;i++)
		if(num[i])f[pos[num[i]]]++;
	Solve();
	return 0;
}