[luogu] [CQOI2013] 新Nim游戏 线性基,排除异或为0的情况

前言

传送门 :

思路

根据 wiki,中所说的第三条线性基性质可知

线性基没有异或和为 0 的子集。

又因为 N i m Nim Nim游戏的先手获胜情况是 a [ i ] ⨁ a [ i + 1 ] . . . . = 0 a[i] \bigoplus a[i+1].... = 0 a[i]⨁a[i+1]....=0

因此我们可以将所有数都加进线性基,当出现 x = = 0 x ==0 x==0的情况就说明可以取走这个 x x x

这样子就会使得原来的集合中不存在 异 或 和 为 0 的 子 集 异或和为0的子集 异或和为0的子集正好对应性质

但是题目中还需要使得第一次取走的最少

由于异或的不进位加法性质,我们考虑从大到小的拿(原因待查,

MyCode

const int N  = 1e5+10;
ll p[N];

ll ans;
bool  XXJ(ll x){
	for(int i = 55 ; i>=0 ; i  --  ){
		if(!(x >> i ))continue;
		
		if(!p[i]){
			p[i] =x;
			break;
		}
		
		x ^=p[i];
		if(!x){
			return false;
		}
	}
	return true;
}
void solve()
{
	int n;cin>>n;
	vector a(n);
	for(int i=1;i>x;a.pb(x);
	}
	sort(all(a),greater());

	for(auto x : a){
		if(!XXJ(x))
		ans+=x;
	}
	if(ans)
	cout