【模板】nim 游戏
题目描述
甲，乙两个人玩 nim 取石子游戏。
nim 游戏的规则是这样的：地上有 \(n\) 堆石子（每堆石子数量小于 \(10^4\)），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 \(n\) 堆石子的数量，他想知道是否存在先手必胜的策略。
输入格式
本题有多组测试数据。
第一行一个整数 \(T\) （\(T\le10\)），表示有 \(T\) 组数据
接下来每两行是一组数据，第一行一个整数 \(n\)，表示有 \(n\) 堆石子，\(n\le10^4\)。
第二行有 \(n\) 个数，表示每一堆石子的数量.
输出格式
共 \(T\) 行，每行表示如果对于这组数据存在先手必胜策略则输出 Yes，否则输出 No。
样例 #1
样例输入 #1
2
2
1 1
2
1 0
样例输出 #1
No
Yes
结论
如果有 \(n\) 堆石子，每堆石子的个数分别为：\(a_1, a_2, a_3, a_4......a_n\)，若： \(a_1 \oplus a_2 \oplus a_3 \oplus a_4 ... \oplus a_n \neq 0\) 则先手必胜，否则先手必输。
操作到最后的时候是 \(0\oplus0\oplus0\oplus...\oplus0=0\)
在操作过程中 如果 \(a_1 \oplus a_2 \oplus a_3 \oplus a_4 ... \oplus a_n \neq 0 = x\) 那么我们可以将结果异变成 \(0\)
证明
不妨设 \(x\) 的二进制最高位 \(1\) 在第 \(k\) 位，那么 \(a_1,a_2,a_3,...,a_n\) 中，必然有一个数字 \(a_i\) 第 \(k\) 位为 \(1\) 。
因为 \(x\) 是异或而来的。\(a_i \oplus x<a_i\) (异或后，第 \(k\) 位会变成 \(0\))。
从第 \(i\) 堆石子拿走 \(a_i-(a_i \oplus x)\) 个石子，第 \(i\) 堆还剩
此时 \(a_1 \oplus a_2 \oplus a_3 \oplus a_4 ... \oplus a_n \oplus x= x \oplus x=0\)
那么这时候通过此项操作，我们可以把操作分为两种情况
1. 如果先手面对的局面是 \(a_1 \oplus a_2 \oplus a_3 \oplus a_4 ... \oplus a_n \neq 0\)，
那么先手总可以通过拿走某一堆若干个石子，将局面变成\(a_1 \oplus a_2 \oplus a_3 \oplus a_4 ... \oplus a_n = 0\)。 后手只能 \(a_1 \oplus a_2 \oplus a_3 \oplus a_4 ... \oplus a_n \neq 0\) 的情况。
由于游戏一定可以结束，从而到最后的时候先手拿走最后一些石子，留给后手无石子可拿,先手必胜。
2. 如果先手面对的局面是 \(a_1 \oplus a_2 \oplus a_3 \oplus a_4 ... \oplus a_n = 0\)
那么无论先手怎么拿，都会将局面变成 \(a_1 \oplus a_2 \oplus a_3 \oplus a_4 ... \oplus a_n \neq 0\)，那么后手总可以通过拿走某一堆若干个石子，将局面变成 \(a_1 \oplus a_2 \oplus a_3 \oplus a_4 ... \oplus a_n = 0\)。
如此重复，最后一定是先手面临最终没有石子可拿的状态。先手必败。
#include <cstdio>
#include <iostream>
using namespace std;
int main()
{
int n;
scanf("%d", &n);
int res = 0;
for (int i = 0; i < n; i++)
{
int x;
scanf("%d", &x);
res ^= x;
}
if (res == 0)
puts("No");
else
puts("Yes");
return 0;
}