记录编号	400536	评测结果	AAAAAAAAAA
题目名称	k次按位异或	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	2.575 s
提交时间	2017-04-30 16:13:07	内存使用	4.29 MiB

#include<cstdio>
const int N=1<<20,U=N-1,p=10007;
int n,k,q,f[N];
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
int dec(int x,int y){x-=y;return x<0?x+p:x;}
int power(int x,int y){
	int ans=1;
	for (;y;y>>=1,x=x*x%p)
		if (y&1) ans=ans*x%p;
	return ans;
}
void fwt(int *a,int n){
	for (int i=2;i<=n;i<<=1){
		int m=i>>1;
		for (int j=0;j<n;j+=i)
		for (int k=0;k<m;k++){
			int x=a[j+k],y=a[j+k+m];
			a[j+k]=inc(x,y);
			a[j+k+m]=dec(x,y);
		}
	}
}
int main()
{
	freopen("k_xor.in","r",stdin);
	freopen("k_xor.out","w",stdout);
	scanf("%d%d",&n,&k);
	for (int i=1;i<=n;i++){
		int x;
		scanf("%d",&x);
		f[x]=inc(f[x],1);
	}
	fwt(f,N);
	for (int S=0;S<=U;S++) f[S]=power(f[S],k);
	fwt(f,N);
	int del=power((p+1)>>1,20);
	for (int S=0;S<=U;S++) f[S]=f[S]*del%p;
	scanf("%d",&q);
	while (q--){
		int x;
		scanf("%d",&x);
		printf("%d\n",f[x]);
	}
	return 0;
}