记录编号	163927	评测结果	WWAWWWWAWW
题目名称	[SDOI 2015] 序列统计	最终得分	20
用户昵称	天一阁	是否通过	未通过
代码语言	C++	运行时间	3.503 s
提交时间	2015-05-27 09:59:34	内存使用	27.01 MiB

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <map>
 
#define N 1000010
#define LL unsigned long long
#define mod 1004535809
#define gn 3
 
using namespace std;

map<int,int> MT;
 
LL qpow(LL x,LL n,LL P){
	LL ans=1;
	for(;n;n>>=1,x=x*x%P)
		if(n&1) ans=ans*x%P;
	return ans;
}
 
int R[N];
 
void fnt(int *x,int n,int t){
	for(int i=0;i<n;i++) if(i<R[i]) swap(x[i],x[R[i]]);
	for(int m=1;m<n;m<<=1){
		LL wn=qpow(gn,(mod-1)/(m<<1),mod);
		if(t==-1) wn=qpow(wn,mod-2,mod);
		for(int k=0;k<n;k+=(m<<1)){
			LL wt=1;
			for(int i=0;i<m;i++,wt=wt*wn%mod){
				int &A=x[i+m+k];
				int &B=x[i+k],t=A*wt%mod;
				A=(B-t+mod)%mod; B=(B+t)%mod;
			}
		}
	}
	if(t==-1){
		for(int i=0;i<n;i++)
			x[i]=x[i]*qpow(n,mod-2,mod)%mod;
	}
}
 
int a0[N],b0[N],c0[N];

void multpoly(int *A,int *B,int *C,int n){
	int nt,L=0;
	for(nt=1;nt<=n+n;nt<<=1) L++;
	for(int i=0;i<nt;i++) R[i]=(R[i>>1]>>1)|((i&1)<<(L-1));
	for(int i=0;i<nt;i++) a0[i]=b0[i]=c0[i]=0;
	for(int i=0;i<n;i++) a0[i]=A[i],b0[i]=B[i];
	fnt(a0,nt,1); fnt(b0,nt,1);
	for(int i=0;i<nt;i++) c0[i]=(a0[i]*(LL)b0[i])%mod;
	fnt(c0,nt,-1);
	for(int i=0;i<nt;i++) C[i]=c0[i];
	for(int i=0;i<nt;i++)
		if(i%(n-1)<i){
			C[i%(n-1)]=(C[i%(n-1)]+C[i])%mod;
			C[i]=0;
		}
}
 
int n,M,X,S,a[N],c[N],gr,p[N],tot_p;
 
int find(int x){
	for(int i=0;i<M;i++)
		if(qpow(gr,i,M)==(LL)x) return i;
	return -1;
}
 
bool check(){
	for(int i=1;i<=tot_p;i++)
		if(qpow(gr,(M-1)/p[i],M)==1LL) return 0;
	return 1;
}
 
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=2;i<=M-1;i++)
		if((M-1)%i==0) p[++tot_p]=i;
	for(gr=2;gr<M;gr++)
		if(check()) break;
	for(int i=0;i<M;i++) MT[(int)qpow(gr,i,M)]=i;
	for(int i=0,x;i<S;i++)
		scanf("%d",&x),a[MT[x]]++;
	c[0]=1;
	for(;n;n>>=1){
		if(n&1) multpoly(c,a,c,M);
		multpoly(a,a,a,M);
	}
	printf("%d\n",c[find(X)]);
	return 0;
}