记录编号	533472	评测结果	AAAAAAAAAAAAAAAAAAAA
题目名称	3197.石子游戏	最终得分	100
用户昵称	bilibili	是否通过	通过
代码语言	C++	运行时间	2.119 s
提交时间	2019-06-26 18:41:27	内存使用	41.02 MiB

#include <cstdio>
#include <algorithm>
#include <cstring>
#define int long long
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(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)/2;
				a[k+len]=(x-y)/2;
			}
		}
	}
}
int n,a[1200100],A[1200100],Xorans=0,B[1200100],C[1200100],maxa,ans;
signed main(){
	freopen("nim.in","r",stdin);
	freopen("nim.out","w",stdout);
	scanf("%lld",&n);
	for(int i=1;i<=n;i++){
		scanf("%lld",&a[i]);
		Xorans^=a[i];
		B[a[i]]=1;
		maxa=max(maxa,a[i]+1);
	}
	int limt=1;
	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]=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;
}