首先，我们需要了解 \(Nim\) 游戏是什么东西。
\(Nim\) 游戏指：两个人，有 \(n\) 堆数，每堆有 \(a_i\) 个，每次可以且仅可以取一堆中的若干个数，求问先手有没有必胜策略（当然两个人都足够聪明）。
首先，先研究显然的必胜策略。比如，我们要得到 \(0\) 这个数，那么当你取完时还剩下 \(0\) 个。
然后，我们通过最后的这个必胜状态，往前递推找出其余的必胜状态。
显然博弈论是必然会出现循环节的，如果每次都可以取到当前这个循环节上的必胜状态，并且让你的对手能达到的下个状态全部都是必败状态，那样你就稳赢。
接着，我们来分析 \(Nim\) 游戏这道题，我们先考虑什么状态下是必胜的：
当 \(n=1\) 的时候，很显然先手必胜，因为先手一次性取完即可。
- 当然，这里当 \(a_1 ≠ 0\)，所以可以理解为 \(a_1 \operatorname{xor} 0=a\)。
当 \(n=2\) 的时候：我们就需要考虑一堆的石头和另一堆的石头相不相等。
- 如果一堆的石头和另一堆相等，那么不论先手取什么，后手都只需要跟着先手取相同的个数就行了。所以很显然就是先手必败。
- 此时我们可以考虑为：\(a_1\operatorname{xor} a_2 = a\)。
如果一堆的石头和另一堆不相等，那么先手就取 \(|a_1-a_2|\)。就必胜了。
然后就转移到了上面那个状态，不过对象换了。
必胜是对于当前这个状态是必胜的，与是谁无关，赢的人只是处于一个胜的状态而已。这是先手必胜。
于是，我们就将这个问题扩展到 \(n\) 上面。
如果当我取完后，每堆石头的数量都为 \(0\)，我胜。
-
即最终的获胜式子为 \(0\operatorname{xor}0\operatorname{xor}0\operatorname{xor}…\operatorname{xor} 0=0\)。
-
我们再来看看它的初始状态，即为 \(a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}…\operatorname{xor}a_n =a\)。
-
我们下一步期望状态应该是 \(newa_1\operatorname{xor}newa_2\operatorname{xor}newa_3\operatorname{xor}…\operatorname{xor}newa_n =a\)。
-
所以很显然，如果任意的一个状态 \(a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}…\operatorname{xor}a_n =a\) 都可以转化成 \(a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}…\operatorname{xor}a_n =0\)，那么这个状态的下一个状态一定是 \(a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}…\operatorname{xor}a_n =aa\)。
-
因为取一堆数的异或和为 \(0\)，并且我们修改其中的一个元素，是无法维持 \(a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}…\operatorname{xor}a_n =0\)。所以下一个状态（即你的对手）一定会变成一个 \(a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}…\operatorname{xor}a_n =newa\) 的状态。
-
但是如果你可以把 \(a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}…\operatorname{xor}a_n =newa\) 的状态转变成 \(newa_1\operatorname{xor}newa_2\operatorname{xor}newa_3\operatorname{xor}…\operatorname{xor}newa_n =0\) 的状态，那么我们就可以把这一次一次操作当一个以 \(2\) 为循环周期的循环节。每次前者取到的值为 \(x(x ≠0)\)，后者取到的值为 \(0\)。
-
最后取到 \(0\operatorname{xor}0\operatorname{xor}0\operatorname{xor}…\operatorname{xor} 0=0\) （即获胜式子）这个式子的一定就是你。
-
因为你的对手没有取到过异或和为 \(0\) 的状态，所以你是必胜的。
-
接下来，我们证明为什么对于任何一个形似 \(a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}…\operatorname{xor}a_n =a\) 的状态都可以转换成 \(newa_1\operatorname{xor}newa_2\operatorname{xor}newa_3\operatorname{xor}…\operatorname{xor}newa_n =0\) 的状态。
- 首先，我们先分析一下整式 \(a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}…\operatorname{xor}a_n =a\)。
- 我们假设 \(a\) 的最高位 为 \(k\)。
- 在异或运算中是不存在进位的，所以这个 \(1\) 肯定是第 \(k\) 位这一位上面算出来的，又因为它是异或，所以在前面的 \(a_1\) 到 \(a_n\) 中必然存在奇数个 \(1\)。
- 我们只需要找到一个数这一位(第 \(k\) 位)为 \(1\) 就行了，多个的话只需要其中一个就行了，另外几个也是可行的方案。
- 现在，我们的目的是将\(a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}…\operatorname{xor}a_n =a\) 的状态转换成 \(newa_1\operatorname{xor}newa_2\operatorname{xor}newa_3\operatorname{xor}…\operatorname{xor}newa_n =0\) 的状态。所以说，如何在异或的一下吧 \(a\) 变成 \(0\) 呢？
- 我们都知道，一个数异或上自己，答案是 \(0\)。那么我们对等式做一下变形，得到：
- \(a\operatorname{xor}a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}a_4=a\operatorname{xor}a=0\)
- 我们接下来要做的是把等式左边的 \(a\) 与一个 \(a_i\) 融合，使得此问题变小一堆，所以 \(a\operatorname{xor} a_i\) 要得到一个 \(<a_i\) 的新数。
- 我们在这之前是不是找到了一个数在 \(a\) 的最高位(第 \(k\) 位)等于 \(1\)，我们设它为 \(a_k\)，它的第 \(k\) 位为 \(1\)。
- 在第 \(k\) 位上，\(a_k\operatorname{xor}a=0\)。又因为 \(a_k\) 的前几位不变，第 \(k\) 位从 \(1 \rightarrow 0\)，所以肯定变小了。 这满足了我们每次从一堆数中取出部分的要求。
- 所以，对于任何一个形似 \(a_1\operatorname{xor}a_2\operatorname{xor}a_3\operatorname{xor}…\operatorname{xor}a_n =a\) 的状态都可以转换成 \(newa_1\operatorname{xor}newa_2\operatorname{xor}newa_3\operatorname{xor}…\operatorname{xor}newa_n =0\) 的状态的问题就被证明了。
-
所以说，我们得到的结论是正确的。即，如果将每堆数相互异或得到的和不为 \(0\) ，则先手必胜。
-
反之，如果将每堆数相互异或得到的和为 \(0\) ，则先手必败。
-
所以，我们可以得到代码。（题目：【模板】Nim 游戏）
#include<bits/stdc++.h>
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+(ch^48);
ch=getchar();
}
return x*f;
}
int main(){
int T=read();
while(T--){
int n=read();
int ans=0;
for(int i=1;i<=n;++i){
int x=read();
ans^=x;
}
if(!ans){
printf("No\n");
}
else{
printf("Yes\n");
}
}
}