记录编号	533479	评测结果	WWWWWWWWWWWWWWWWWWWW
题目名称	3197.石子游戏	最终得分	0
用户昵称	bilibili	是否通过	未通过
代码语言	C++	运行时间	3.241 s
提交时间	2019-06-26 19:04:06	内存使用	21.97 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
void FWT(int *a,int n){
	for(int i=2;i<=n;i<<=1){
		int len=i/2;
		for(int j=0;j<n;j+=i){
			for(int k=j;k<j+len;k++){
				int x=a[k],y=a[k+len];
				a[k]=x+y;
				a[k+len]=x-y;
			}
		}
	}
}
void IFWT(long long *a,int n){
	for(int i=2;i<=n;i<<=1){
		int len=i/2;
		for(int j=0;j<n;j+=i){
			for(int k=j;k<j+len;++k){
				long long x=a[k],y=a[k+len];
				a[k]=(x+y)/2;
				a[k+len]=(x-y)/2;
			}
		}
	}
}
int n,a[(1<<20)],A[(1<<20)],Xorans=0,B[(1<<20)],maxa,ans;
long long C[(1<<20)];
signed main(){
	freopen("nim.in","r",stdin);
	freopen("nim.out","w",stdout);
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		Xorans^=a[i];
		B[a[i]]=1;
		maxa=max(maxa,a[i]+1);
	}
	int limt=(1<<19);
//	while(limt<=maxa)
//		limt<<=1;
	ans=n;
	FWT(B,limt);
	A[0]=1;
	while(!A[Xorans]){
		ans--;
		FWT(A,limt);
		for(int i=0;i<limt;i++)
			C[i]=1LL*A[i]*B[i];
		IFWT(C,limt);
		for(int i=0;i<limt;i++)
			A[i]=(C[i]>0);
	}	
	printf("%lld\n",ans);
	return 0;
}