【BZOJ 3105】[cqoi2013] 新Nim游戏

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=3105

这个题目，考虑两个回合之后。
假如对手能够在在第二个回合搞出一个Nim和为0的东西，那我们岂不是输了？
所以我们不能给对手搞出Nim和为0的机会，而Nim和为Xor，不存在子集Nim和为0是线性无关
而我们又要子集最大（损失最小），所以我们要求的是一个极大线性无关子集
然后我们发现，这货不是线性基吗？
于是水之

#include<bits/stdc++.h>
#define LL long long
using namespace std;

inline int read(){
	char c=getchar(); int ret=0,f=1;
	while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
	while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
	return ret*f;
}

int bas[32],arr[109];
inline bool update(int w) {
	for (int i=0;i<=31;i++) if (w & 1<<i) 
		if (bas[i]) w ^= bas[i];
		else {bas[i] = w; return 1;}
	return 0;
}

int main(){
	int k = read(); LL vout = 0; 
	for (int i=1;i<=k;i++) arr[i] = read(), vout += arr[i];
	sort(arr+1,arr+1+k);
	for (int i=k;i;i--) vout -= update(arr[i])*arr[i];
	printf("%lld\n",vout);
	return 0;
}