记录编号	266719	评测结果	AAAAAAAAAA
题目名称	异化多肽	最终得分	100
用户昵称	stdafx.h	是否通过	通过
代码语言	C++	运行时间	3.321 s
提交时间	2016-06-09 10:50:19	内存使用	3.29 MiB

#define maxn 262144ul

#include <stdio.h>
#include <string.h>
#include <algorithm>

const int G=5,mod=1005060097;

inline int ksm(int p,int k){
	int ret=1;
	while(k){
		if(k&1) ret=1ll*ret*p%mod;
		k>>=1,p=1ll*p*p%mod;
	} return ret;
}

void ntt(int *f,int n,int flag){
	for(int i=0,j=0;i<n;i++){
		if(i>j) std::swap(f[i],f[j]);
		for(int t=n>>1;(j^=t)<t;t>>=1);
	} int u,t,wn,w;
	for(int m=2;m<=n;m<<=1){
		w=1,wn=ksm(G,flag==1?(mod-1)/m:(mod-1-(mod-1)/m));
		for(int i=0,p=m>>1;i<n;i+=m,w=1) for(int k=0;k<p;k++,w=1ll*w*wn%mod)
		    u=f[i+k],t=1ll*f[i+k+p]*w%mod,f[i+k]=(u+t)%mod,f[i+k+p]=(u-t)%mod;
	}
	if(flag==-1){
		int inv=ksm(n,mod-2);
		for(int i=0;i<n;i++) f[i]=1ll*f[i]*inv%mod;
	} return;
}

void poly_inv(int *f,int *g,int n){
	if(n==1){ g[0]=ksm(f[0],mod-2); return; }
	static int tmp[maxn];
	poly_inv(f,g,n>>1),memcpy(tmp,f,sizeof(f[0])*n);
	memset(tmp+n,0,sizeof(f[0])*n),ntt(tmp,n<<1,1),ntt(g,n<<1,1);
   	for(int i=0;i<(n<<1);i++) tmp[i]=1ll*g[i]*(2ll-1ll*g[i]*tmp[i]%mod)%mod;
    ntt(tmp,n<<1,-1); for(int i=0;i<n;i++) g[i]=tmp[i];
    memset(g+n,0,sizeof(g[0])*n); return;
}

int n,N,m,iv[maxn],rp[maxn];

void read(int &x){
	x=0; int c=getchar(); for(;c<'0'||c>'9';c=getchar());
	for(;c>='0'&&c<='9';c=getchar()) x=(x<<1)+(x<<3)+(c^48); return;
}

int main(){
	freopen("polypeptide.in","r",stdin);
	freopen("polypeptide.out","w",stdout);
	read(n),read(m);
	for(int i=1,x;i<=m;i++) read(x),--iv[x]; iv[0]++;
	for(N=1;N<=n;N<<=1); poly_inv(iv,rp,N);
	printf("%d\n",(rp[n]%mod+mod)%mod); return 0;
}