记录编号	163800	评测结果	AAAAAAAAAA
题目名称	[SDOI 2015] 序列统计	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	1.276 s
提交时间	2015-05-26 14:39:43	内存使用	5.21 MiB

/*****************************************************************************/
/******************************Designed By Asm.Def****************************/
/*****************************************************************************/
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <ctime>
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) )
#define FREAD
#define FREADLENTH 5000000
#ifdef FREAD
char *fread_ptr = (char*)malloc(FREADLENTH);
#define getc() (*(fread_ptr++))
#else
#define getc() getchar()
#endif
using namespace std;
template<class T>inline void getd(T &x){
	int ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')neg = true, ch = getc();
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/*******************************************************************************/
const int maxn = 8005, mod = 1004535809;
typedef long long LL;

int N, M, Len, Len_1, log2Len, X, e, e_1, Ind[maxn];

inline int powmod(int a, int n){
	int ans = 1;
	while(n){
		if(n & 1)ans = (LL)ans * a % mod;
		a = (LL)a * a % mod;
		n >>= 1;
	}
	return ans;
}
#define inv(x) (powmod(x, 1004535807))

struct Poly{int A[maxn << 2];}F;

inline void init(){
	int s, i, j, a, g;
	getd(N), getd(M), getd(X), getd(s);
	bool ok = 0;
	for(i = 2;!ok;++i){
		ok = 1;
		for(j = 1, a = i;j < M-1;++j, a = (LL)a * i % M)if(a == 1){
			ok = 0;
			break;
		}
		if(ok)g = i;
	}
	for(i = 0, a = 1;i < M-1;++i, a = (LL)a * g % M)Ind[a] = i;
	X = Ind[X];
	while(s--){
		getd(a);
		if(a)F.A[Ind[a]] = 1;
	}
	i = 1, j = 2;
	while(j < M-1)++i, j <<= 1;++i, j <<= 1;
	Len = j;log2Len = i;
	Len_1 = inv(Len);
	e = powmod(3, (mod-1) >> i);
	e_1 = inv(e);
}

inline void Reverse(int *A){
	int i, j, rev;
	for(i = 1, rev = Len>>1;i < Len-1;++i){
		if(i < rev)swap(A[i], A[rev]);
		for(j = Len>>1;rev & j;j >>= 1)rev ^= j;rev ^= j;
	}
}

inline void Trans(Poly &A, int x){
	Reverse(A.A);
	int l, i, j, k, a, px, *x1, *x2, t;
	static int pow2x[20];
	for(i = 0, a = x;i < log2Len;++i, a = (LL)a * a % mod)pow2x[i] = a;
	for(l = 1,i = 0;l < Len;l <<= 1,++i){
		px = pow2x[log2Len-i-1];
		for(j = 0;j < Len;j += (l<<1))for(k = 0,a = 1;k < l;++k){
			x1 = A.A + j + k;x2 = x1 + l;
			t = (LL)a * (*x2) % mod;
			*x2 = (*x1 + mod - t) % mod;
			*x1 = (*x1 + t) % mod;
			a = (LL)a * px % mod;
		}
	}
}

inline void operator *= (Poly &a, Poly b){
	Trans(a, e);Trans(b, e);
	int i, m = M-1, t;
	for(i = 0;i < Len;++i)a.A[i] = (LL)a.A[i] * b.A[i] % mod;
	Trans(a, e_1);
	for(i = 0;i < Len;++i)a.A[i] = (LL)a.A[i] * Len_1 % mod;
	for(i = m, t = 0;i < Len;++i, ++t){
		if(t == m)t = 0;
		a.A[t] = (a.A[t] + a.A[i]) % mod;
		a.A[i] = 0;
	}
}

//inline void print(Poly &x){for(int i = 0;i < Len;++i)printf("%d ", x.A[i]);puts("");}
inline void pow2(Poly &a){
	Trans(a, e);
	int i, m = M-1, t;
	for(i = 0;i < Len;++i)a.A[i] = (LL)a.A[i] * a.A[i] % mod;
	Trans(a, e_1);
	for(i = 0;i < Len;++i)a.A[i] = (LL)a.A[i] * Len_1 % mod;
	for(i = m, t = 0;i < Len;++i, ++t){
		if(t == m)t = 0;
		a.A[t] = (a.A[t] + a.A[i]) % mod;
		a.A[i] = 0;
	}
}
inline void work(){
	Poly Ans = {{0}};Ans.A[0] = 1;

	//print(Ans);

	while(N){
		if(N & 1)Ans *= F;
		//printf("F1=");print(F);
		pow2(F);
		//printf("F2=");print(F);
		N >>= 1;
	}
	printf("%d\n", Ans.A[X]);
}

int main(){

#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#else
	SetFile(sdoi2015_sequence);
#endif
#ifdef FREAD
	fread(fread_ptr, 1, FREADLENTH, stdin);
#endif

	init();
	work();

#ifdef DEBUG
	printf("\n%.3lf sec\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}