[ARC168B] Arbitrary Nim

原题链接：ARC168B

题意：有 \(n\) 堆石子，每堆有 \(a_{i}\) 个。每人每次可以取走其中一堆中的 \(x(1 \le x \le k)\) 个。求出一个最大的 \(k\) 使得先手必胜。无解输出 \(0\)，\(k\) 可以取无限大输出 \(-1\)。

一个经典 Nim 游戏的结论是：\(a_{i}\) 的异或和为 \(0\)，则先手必败。但是现在限制了一次最多取 \(k\) 个，所以我们可以先把每一个 \(a_{i}\) 模上 \(k+1\)，然后这就变成了一个经典博弈。

首先考虑如何判断 \(-1\) 的情况。显然，如果当前异或和已经不为 \(0\) 了，那么无论 \(k\) 取多大，异或值一定不为 \(0\)，所以 \(k\) 可以取无限大。

再来考虑 \(0\) 的情况。我们会发现，两个相同的 \(a_{i}\) 无论模上多少最终的值都一定相同，即最终的异或和一定为 \(0\)，所以我们可以先消除掉出现次数为偶数的数（因为异或和为 \(0\) 的数对最终的异或值没有影响），如果这时已经没有数了，说明最终的异或和一定为 \(0\)，则先手必败。

现在就只剩下一些出现次数为奇数的数了，且这些数的异或和为 \(0\)（否则为上述 \(-1\) 的情况）。假设其中的最大值为 \(p\)，其余值的异或和等于 \(q\)，那么 \(p \oplus q = 0\)。这时将 \(k\) 设为 \(p-1\)，将所有数模上 \(p\) 之后，只有 \(p\) 变为了 \(0\)，其余数不变。因为 \(p \oplus q = 0\)，所以 \(0 \oplus q \ne 0\)，所以这时先手必胜，\(k\) 取 \(p-1\)。

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int MAXN = 3e5 + 10;
int n,a[MAXN],k = 0;
set <int> s;
signed main()
{
	cin >> n;
	for(int i = 1;i <= n;i++)
	{
		cin >> a[i];
		if(s.find(a[i]) != s.end()) s.erase(a[i]);
		else s.insert(a[i]);
		k ^= a[i];
	}
	if(k != 0) cout << "-1";
	else if(s.size() == 0) cout << "0";
	else cout << *--s.end() - 1;
	return 0;
}