记录编号	376949	评测结果	AAAAAAAAAA
题目名称	异化多肽	最终得分	100
用户昵称	‎MistyEye	是否通过	通过
代码语言	C++	运行时间	3.989 s
提交时间	2017-02-28 17:12:15	内存使用	4.32 MiB

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn = (1<<18)+11;
const int G = 5, mod = 1005060097, phi = mod-1;
int N, M, F[maxn], H[maxn], rev[maxn];
int fpow(int x, int y) {
	int ans = 1;
	for(; y; y>>=1, x=1LL*x*x%mod)
		if(y&1) ans = 1LL*x*ans%mod;
	return ans;
}
void NTT(int *a, int n, int op) {
	int l = 0; while((1<<l)<n) ++l; --l;
	for(int i=1; i<n; ++i) {
		rev[i] = rev[i>>1]>>1|((i&1)<<l);
		if(rev[i]>i) swap(a[i], a[rev[i]]);
	}
	for(int k=2; k<=n; k<<=1) {
		ll w, wn = fpow(G, (phi/k*op%phi+phi)%phi);
		for(int j=0; w=1, j<n; j+=k) {
			for(int i=0; i<(k>>1); ++i, w=w*wn%mod) {
				ll t = a[i+j+(k>>1)]*w%mod;
				a[i+j+(k>>1)] = (a[i+j]+mod-t)%mod;
				a[i+j] = (a[i+j]+t)%mod;
			}
		}
	}
	if(op!=1) {
		ll inv = fpow(n, mod-2);
		for(int i=0; i<n; ++i) a[i] = inv*a[i]%mod;
	}
}
void Poly_inv(int *a, int *b, int n) {
	if(n==1) { b[0] = fpow(a[0], mod-2); return; }
	static int t[maxn];
	Poly_inv(a, b, n>>1);
	memcpy(t, a, sizeof(a[0])*n);
	NTT(t, n<<1, 1);
	NTT(b, n<<1, 1);
	for(int i=0; i<(n<<1); ++i) 
		b[i] = b[i]*(2-1LL*b[i]*t[i]%mod)%mod;
	NTT(b, n<<1, -1);
	memset(b+n, 0, sizeof(a[0])*n);
}
signed main() {
	freopen("polypeptide.in","r",stdin);
	freopen("polypeptide.out","w",stdout);
	scanf("%d%d", &N, &M);
	for(int i=1, v; i<=M; ++i) 
		scanf("%d", &v), F[v] -= 1;	++F[0];
	int n = 1; while(n<=N) n <<= 1;
	Poly_inv(F, H, n);
	printf("%d\n", (H[N]%mod+mod)%mod);
	getchar(), getchar();
	return 0;
}