【题解】SDOI2015序列统计
来自永不AFO的YYB的推荐
这里是乘积，比较麻烦，不过由于给定的序列膜数是个小质数，所以可以(O(m^2log m))找原跟(实际上不需要这么多)。
乘积有点麻烦，转换成加法就好了，然后取离散对数(a_iequiv g^{c_i} mod m)，现在每个元素都用原根的指数代替了，问题就转变成了有多少种方案使得每个元素的乘积等于(log xmod m)。
根据题意直接构造
[F(x)=sum [exist log a_i=i]x^i
]
答案就是
[F(x)^n
]
吗？
其实要魔改一下，乘的过程中要不断地让(F(x))大于(x^m)的系数算到(x^{i mod m})上，原因显然，略。
不能这么敷衍，到时候自己看会一头雾水，取膜的原因是，我们利用的是多项式乘法的组合意义，现在组合意义是要得到(c_i=sum_limits{k+j equiv i mod m}a_kb_j)，所以如此。
既然要不断地让(F(x))对(x^m)取膜，所以(ln ,exp)废了
直接写两个(log)快速幂跑得飞快
//@winlere
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<vector>
using namespace std; typedef long long ll;
inline int qr(){
register int ret=0,f=0;
register char c=getchar();
while(c<48||c>57)f|=c==45,c=getchar();
while(c>=48&&c<=57) ret=ret*10+c-48,c=getchar();
return f?-ret:ret;
}
int n,m,x,s,g;
vector < int > ve;
const int maxn=8009;
int lg[maxn];
int read[1<<19|1];
int ans[1<<19|1];
namespace poly{
const int maxn=1<<19|1;
int a[maxn],b[maxn],r[maxn];
int savlen;
inline void getr(const int&len){
if(len==savlen)return;
int cnt=0;
for(register int t=1;t<len;t<<=1)++cnt;
for(register int t=1;t<len;++t)
r[t]=r[t>>1]>>1|(t&1)<<cnt>>1;
}
const int mod=1004535809;
const int g=3;
inline int ksm(int base,ll p){
register int ret=1;
for(base%=mod;p;p>>=1,base=1ll*base*base%mod)
if(p&1) ret=1ll*ret*base%mod;
return ret;
}
const int gi=ksm(3,mod-2);
inline void NTT(int*a,const int&len,const int&tag){
getr(len);
for(register int t=1;t<len;++t)
if(r[t]>t) swap(a[t],a[r[t]]);
int *a1,*a0,s=g;
if(tag!=1) s=gi;
for(register int t=1,wn;t<len;t<<=1){
wn=ksm(s,(mod-1)/(t<<1));
for(register int i=0;i<len;i+=t<<1){
a1=(a0=a+i)+t;
for(register int j=0,w=1,tm;j<t;++j,++a1,++a0,w=1ll*w*wn%mod){
tm=1ll**a1*w%mod;
*a1=(*a0-tm)%mod;
*a0=(*a0+tm)%mod;
if(*a1<0)*a1+=mod;
}
}
}
if(tag!=1)
for(register int t=0,in=ksm(len,mod-2);t<len;++t)
a[t]=1ll*a[t]*in%mod;
}
inline void print(int*a,int len){
for(register int t=0;t<len;++t)
printf("%d ",a[t]);
putchar('
');
}
inline void KSM(int*a,int*b,const int&len,int p){
static int ret[maxn],base[maxn];
memset(ret,0,sizeof ret);
memset(base,0,sizeof base);
ret[0]=1;
for(register int t=0;t<len;++t) base[t]=a[t];
while(p){
NTT(base,len<<1,1);
if(p&1){
NTT(ret,len<<1,1);
for(register int t=0;t<len<<1;++t) ret[t]=1ll*ret[t]*base[t]%mod;
NTT(ret,len<<1,-1);
for(register int t=(len<<1)-1;t-m+1>=0;--t) ret[t-m+1]=(ret[t-m+1]+ret[t])%mod,ret[t]=0;
}
for(register int t=0;t<len<<1;++t) base[t]=1ll*base[t]*base[t]%mod;
NTT(base,len<<1,-1);
for(register int t=(len<<1)-1;t-m+1>=0;--t) base[t-m+1]=(base[t-m+1]+base[t])%mod,base[t]=0;
p>>=1;
}
for(int t=0;t<len;++t) b[t]=ret[t];
}
}
inline int ksm(const int&base,const int&p,const int&mod=m){
register int ret=1;
for(register int t=p,b=base%mod;t;t>>=1,b=1ll*b*b%mod)
if(t&1) ret=1ll*ret*b%mod;
return ret;
}
inline void findg(){
#define mod m
int k=m-1;
for(register int t=2;1ll*t*t<=k;++t){
if(k%t==0){
ve.push_back(t);
if(k/t!=t) ve.push_back(k/t);
}
}
//for(auto f:ve) cout<<"fac="<<f<<endl;
for(register int t=2;;++t){
int l=1;
for(auto f:ve)
if(ksm(t,f)==1) l=0;
if(l) {g=t;return;}
}
#undef mod
}
int main(){
freopen("sdoi2015_sequence.in","r",stdin);
freopen("sdoi2015_sequence.out","w",stdout);
n=qr();m=qr();x=qr();s=qr();
findg();
for(register int t=1,k=g;t<m-1;++t,k=1ll*k*g%m) lg[k]=t;
for(register int t=1;t<=s;++t) {int t1=qr();if(t1)read[lg[t1]]=1;}
int k=1;
while(k<=m) k<<=1;
poly::KSM(read,read,k,n);
//for(register int t=0;t<k;++t) cout<<read[t]<<' ';
//cout<<endl;
int ans=read[lg[x]];
printf("%d
",ans);
return 0;
}