kill.cpp

#include <cstdio>
#include <cstring>
#include <algorithm>
#define N 2000
#define maxn 1000100
#define intl long long
using namespace std;

int i,j,k,l,m,n,T,v[maxn];
intl Mo,fac[maxn + 4010],ni[maxn + 4010],g[4010],f[4010],s[2010],js,ans;

intl ksm(intl a,int k) {
	intl ans = 1;
	while (k) {
		if (k & 1) ans *= a, ans %= Mo;
		(a *= a) %= Mo;
		k >>= 1;
	}
	return ans;
}

void init() {
	fac[0] = f[0] = 1;
	for (i = 1; i <= n + 4000; i++) fac[i] = fac[i - 1] * (intl)i, fac[i] %= Mo;

	for (i = 0; i <= n + 4000; i++) ni[i] = ksm(fac[i],Mo - 2);
}

intl C(int a,int b) {
	return (fac[a] * ni[b] % Mo * ni[a - b] % Mo);
}

int main() {
	freopen("kill.in","r",stdin);
	freopen("kill.out","w",stdout);
	scanf("%d %d %lld",&n,&T,&Mo);
	init();
	for (i = 1; i <= n; i++) scanf("%d",&j),v[j]++;

	for (i = 1; i <= N; i++) {
		for (j = 0; j <= N; j++) g[j] = f[j], f[j] = 0;
		for (j = 0; j <= v[i]; j++) {
			js = j & 1 ? -1 : 1;
			for (k = 0; k + j * (i + 1) <= N; k++)
				(f[k + j * (i + 1)] += js * g[k] % Mo * C(v[i],j)) %= Mo;
		}
	}

	for (i = 0; i <= N; i++) s[i] = C(n + i - 1,i);
	for (; T; T--) {
		scanf("%d",&k);
		ans = 0;
		for (i = 0; i <= k; i++) (ans += f[i] * s[k - i]) %= Mo;
		ans = (ans + Mo) % Mo;
		printf("%lld\n",ans);
	}

	return 0;
}