[模板]Nim游戏
题目描述
甲，乙两个人玩Nim取石子游戏。
nim游戏的规则是这样的：地上有n堆石子（每堆石子数量小于10000），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这n堆石子的数量，他想知道是否存在先手必胜的策略。
结论：所有石子异或和为0则先手必败
证明：
\(1\):输的状态最后肯定是每堆都没有石子，此时所有石子异或和为\(0^0^0^0......^0 = 0\)
\(2\):我们设所有石子的异或和为\(k\)，\(k\)的最高位为第\(i\)位，则其中必定有一堆石子的第\(i\)位为\(i\)(异或的性质)，我们设这堆石子为\(H\)，其余所有石子异或和为\(x\)，那么\(H\)^\(x\)\(=\)\(k\)，那么有\(H\)^\(k\)\(=\)\(x\)，所以(\(H\)^\(k\))^\(x\)\(=\)\(0\)。
\(3\):所以我们得出：如果先手异或和不为\(0\)，可以一步让后手的情况为异或和为\(0\)；如果先手异或和为\(0\)，那么后手异或和就不为\(0\)
\(4\):现在假设开始时所有石子的异或和不为\(0\)，则先手可以一直让后手的异或和为\(0\)(也就是\(2\)中的操作)，最终后手会走向所有石子都是\(0\)的情况，则后手败，反之开始时所有石子的异或和为\(0\)，那么后手也可以使得先手的异或和一直为\(0\)，那么先手最终会走向所有石子都是\(0\)的情况，则先手败。
所以结论得以证明。
#include <cstdio>
#include <iostream>
using namespace std;
int T,n,ans;
int main()
{
scanf("%d",&T);
while(T --)
{
scanf("%d",&n);
ans = 0;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
ans ^= x;
}
if(ans)
printf("Yes\n");
else printf("No\n");
}
return 0;
}