记录编号	163801	评测结果	AAAAAAAAAA
题目名称	[SDOI 2015] 序列统计	最终得分	100
用户昵称	cstdio	是否通过	通过
代码语言	C++	运行时间	2.845 s
提交时间	2015-05-26 15:51:58	内存使用	0.85 MiB

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
typedef long long LL;
const int SIZE=20010;
LL Real_Mod(LL a,LL m){
	a%=m;
	if(a<0) a+=m;
	return a;
}
LL Quick_Pow(LL a,LL n,LL m){
	LL ans=1;
	while(n){
		if(n&1) ans=Real_Mod(ans*a,m);
		a=Real_Mod(a*a,m);
		n>>=1;
	}
	return ans;
}
LL Inverse(LL a,LL m){//要求a是质数
	return Quick_Pow(a,m-2,m);
}
class Poly{
public:
	static const LL MOD=1004535809;
	static const LL G=3;
	int n;
	LL s[SIZE];
	void print(void)const{
		for(int i=0;i<n;i++){cout<<s[i]<<" ";}cout<<endl;
	}
	void clear(void){
		n=0;
		memset(s,0,sizeof(s));
	}
	inline void Rader_Transform(void){
		int j=0,k;
		for(int i=0;i<n;i++){
			if(j>i) swap(s[j],s[i]);
			k=n;
			while(j&(k>>=1)) j&=~k;
			j|=k;
		}
	}
	void NTT(bool type){//type=1是系数求点,type=0是点求系数
		Rader_Transform();
		for(int step=1;step<n;step<<=1){
			LL wn=Quick_Pow(G,(MOD-1)/(step<<1),MOD);
			if(!type) wn=Quick_Pow(G,MOD-1-(MOD-1)/(step<<1),MOD);
			LL wk=1;
			for(int k=0;k<step;k++){
				for(int Ek=k;Ek<n;Ek+=step<<1){
					int Ok=Ek+step;
					LL t=Real_Mod(wk*s[Ok],MOD);
					s[Ok]=Real_Mod(s[Ek]-t,MOD);
					s[Ek]=Real_Mod(s[Ek]+t,MOD);
				}
				wk=Real_Mod(wn*wk,MOD);
			}
		}
		if(!type){
			LL inv=Inverse(n,MOD);
			for(int i=0;i<n;i++) s[i]=Real_Mod(s[i]*inv,MOD);
		}
	}
	void operator *= (const Poly &a){
		static Poly b;
		b=a;
		int m=1;
		while(m<n+b.n) m<<=1;
		n=b.n=m;
		NTT(true);
		b.NTT(true);
		for(int i=0;i<n;i++) s[i]=Real_Mod(s[i]*b.s[i],MOD);
		NTT(false);
	}
	void Normalize(int P){//质数P的原根表示
		for(int i=n-1;i>=P-1;i--){
			s[i%(P-1)]=Real_Mod(s[i%(P-1)]+s[i],MOD);
			s[i]=0;
		}
		n=P-1;
	}
};
int N,M,X,S,rt;
Poly A;
Poly ans;
int ind[SIZE];
Poly Quick_Pow(Poly a,int n){
	Poly ans;
	ans.clear();
	ans.n=1;
	ans.s[0]=1;
	while(n){
		if(n&1) ans*=a;
		a*=a;
		ans.Normalize(M);
		a.Normalize(M);
		n>>=1;
	}
	return ans;
}
bool Is_Root(int x){
	for(int i=2;i*i<=M-1;i++){
		if((M-1)%i==0){
			if(Quick_Pow(x,i,M)==1) return false;
			if(Quick_Pow(x,(M-1)/i,M)==1) return false;
		}
	}
	return true;
}
int Find_Root(void){
	for(int i=2;i<M;i++){
		if(Is_Root(i)) return i;
	}
	return -1;
}
void Work(void){
	ans=Quick_Pow(A,N);
	printf("%lld\n",ans.s[ind[X]]);
}
void Init(void){
	scanf("%d%d%d%d",&N,&M,&X,&S);
	rt=Find_Root();
	for(int i=0,now=1;i<M-1;i++,now=Real_Mod(now*rt,M)) ind[now]=i;
	A.clear();
	A.n=M-1;
	int t;
	for(int i=1;i<=S;i++){
		scanf("%d",&t);
		t%=M;
		if(t==0) continue;
		A.s[ind[t]]++;
	}
}
int main(){
	freopen("sdoi2015_sequence.in","r",stdin);
	freopen("sdoi2015_sequence.out","w",stdout);
	Init();
	Work();
	return 0;
}