记录编号	373180	评测结果	AAAAAAAAAA
题目名称	异化多肽	最终得分	100
用户昵称	半汪	是否通过	通过
代码语言	C++	运行时间	2.440 s
提交时间	2017-02-20 12:16:53	内存使用	7.82 MiB

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int mod=1005060097;
const int gn=5;
const int maxn=281000;
int p[maxn],inv_p[maxn],N=1,wn[maxn],rev_bit[maxn],Pow[maxn][2],inv_k[maxn]; 
int pow(int a,int b,int mod){
	int ans=1;
	for(;b;b>>=1,a=(a*1ll*a)%mod)if(b&1)ans=(ans*1ll*a)%mod;
	return ans;
}
void before(){
	for(int k=2;k<=N*2;k<<=1){
		Pow[k][1]=pow(gn,(mod-1)/k,mod),Pow[k][0]=pow(Pow[k][1],mod-2,mod);
		inv_k[k]=pow(k,mod-2,mod);
	}
}
void FFT(int r[],int n,int type){
	int i,j,k;
	rev_bit[0]=0;rev_bit[1]=(n>>1);
	for(int i=2;i<n;i++)rev_bit[i]=(rev_bit[i>>1]>>1)+(i&1)*(n>>1);
	for(int i=0;i<n;i++)if(i<rev_bit[i])swap(r[i],r[rev_bit[i]]);
	int gnn,g;
	for(k=2;k<=n;k<<=1)
		for(gnn=Pow[k][type],j=0;j<n;j+=k)
			for(g=1,i=0;i<(k>>1);i++,g=(g*1ll*gnn)%mod){
				int temp1=r[i+j],temp2=(r[i+j+(k>>1)]*1ll*g)%mod;
				r[i+j]=(temp1+temp2)%mod;
				r[i+j+(k>>1)]=(temp1-temp2+mod)%mod;
			}
	if(type==0){
		for(int i=0;i<n;i++)r[i]=(r[i]*1ll*inv_k[n])%mod;
	}
}
void get_inv(int r[],int inv[],int n){
	inv[0]=pow(r[0],mod-2,mod);
	memset(wn,0,sizeof(wn));
	for(int k=2;k<=n;k<<=1){
	//	cout<<k<<endl;
		memcpy(wn,r,sizeof(int)*k);
		memset(wn+k,0,sizeof(int)*k);
	//	for(int i=0;i<k;i++)cout<<wn[i]<<" ";cout<<endl;
	//	for(int i=0;i<k;i++)cout<<inv[i]<<" ";cout<<endl;
		FFT(inv,(k<<1),1);FFT(wn,(k<<1),1);	
		for(int i=0;i<(k<<1);i++){
			inv[i]=(2ll*inv[i]-((inv[i]*1ll*inv[i])%mod*1ll*wn[i])%mod+mod)%mod;	
		}
		FFT(inv,(k<<1),0);
	//	for(int i=0;i<(k<<1);i++)cout<<inv[i]<<" ";cout<<endl;
		memset(inv+k,0,sizeof(int)*k);
	}
}
int main(){
	freopen("polypeptide.in","r",stdin);freopen("polypeptide.out","w",stdout);
	int n,m;
	scanf("%d%d",&n,&m);
	while(N<n+1)N*=2;
	before();
	for(int i=1;i<=m;i++){
		int x;
		scanf("%d",&x);p[x]++;
	}
	p[0]=(p[0]-1+mod)%mod;
	get_inv(p,inv_p,N);
	printf("%d",mod-inv_p[n]);
    return 0;
}