前置知识
\(\operatorname {mex}\)：没有出现过的最小自然数，如 \(\operatorname {mex} \{0,2,3\}=1\)。
\(\oplus\)：按位异或。
前言
博弈类问题大致分为，公平组合游戏、非公平组合游戏（绝大多数的棋类游戏）、反常游戏。
只需要关注公平组合游戏 \(\texttt{(ICG)}\)，反常游戏是公平组合游戏的变形，经济类博弈也不是博客所讨论的范围
- 两个玩家轮流行动且游戏方式一致。
- 两个玩家对状况完全了解。
- 游戏一定会在有限步数内分出胜负。
- 游戏以玩家无法行动结束。
博弈的双方都被认为是神之个体，因为所有玩家对状况完全了解，且充分为自己打算，绝对理性
当局面确定，结果必然注定，并且没有任何随机的成分
游戏中的每一个状态，最终导致的结果也必然注定，只有必胜态、必败态，两种状态
这一类博弈问题的结果没有任何意外，一方可以通过努力去改变结果是不可能的，这一点是反直觉的。
- 常用对数器打表来找规律。
- 博弈论的题目就是 要干去干，去找规律，不要怕。
巴什博弈 \(\texttt{(Bash)}\)
\(n\) 个的石头，每次操作可以拿走 \([1,m]\) 个石头。拿到最后 \(1\) 个石头的人获胜（也就是不能拿石头的人输）。
这个问题特别简单，就是显然答案是如果 \(n\) 为 \(m+1\) 的倍数那么先手输，否则先手赢。
\(\texttt{sg}\) 函数
接下来引入 \(\texttt{sg}\) 函数。
\(\texttt{sg}\) 表示当前状态的胜负情况。
有如下公式 \(sg(A)=\operatorname {mex} (sg(B)|A\to B)\)。
式子中的 \(A\) 和 \(B\) 表示状态，\(A\to B\) 表示 \(A\) 状态可以达到 \(B\)状态。也就是说我们可以通过 \(A\) 能达到的状态的SG函数值推算出 \(A\) 的 \(SG\) 值。
如果 \(\texttt{sg}\) 值为 \(0\) 则表示先手输，否则先手赢。
数学归纳法证明：
- 最终状态 \(SG=0\)。
- 对于任意一个必胜态 \(SG\not=0\)，存在一个后继态 \(SG=0\)
- 对于任意一个必败态 \(SG=0\)，不存在一个后继态 \(SG=0\)。
\(\texttt{e.g.}\)：在巴什博奕中：当 \(m = 2\) 时，\(\texttt{sg[0]=0,sg[1]=1,sg[2], sg[3]=0,}\cdots\)。
\(\texttt{FAQ}\):
- Q: 不就是判断一个输赢吗？为什么要用一个 \(\texttt {int}\)，我 \(\texttt{bool}\) 也可以啊。
- A: 是的，确实可以只有 \(\texttt{bool}\)，用 \(\texttt{int}\) 另有用途，我们下面会讲。
P2197 【模板】\(\texttt{(Nim)}\) 游戏———\(\texttt{sg}\) 多个独立的子问题的合并
题目描述
甲，乙两个人玩 \(\texttt{nim}\) 取石子游戏。
\(\texttt{nim}\) 游戏的规则是这样的：地上有 \(n\) 堆石子（每堆石子数量小于 \(10^4\)），每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。假如甲是先手，且告诉你这 \(n\) 堆石子的数量，他想知道是否存在先手必胜的策略。
公式引入
若局面X由若干个子游戏 \(X1,X2...Xn\) 构成，则
\(SG(x)=SG(X_1)\oplus SG(X_2) \oplus \cdots\oplus SG(X_n)\)
数学归纳法证明：
- 最终局面成立
- \(\forall X\)，所有后继局面可以取到 \(G(X_1)\oplus SG(X_2) \oplus \cdots\oplus SG(X_n)-1\)，取不到\(SG(X_1)\oplus SG(X_2) \oplus \cdots \oplus SG(X_n)\)
同样看做 \(\texttt{Nim}\) 游戏
设 \(S \rightarrow S_1\)
\(S \oplus (S \oplus S_1) =S_1\)
设 \((S \oplus S_1)\) 最高位为 \(k\)，存在 \(A\) 使得 \(k\) 位为 \(1\)。
那么\(A \oplus (S \oplus S_1) < A\)，所以让 \(A\) 变成\(A \oplus (S \oplus S_1)\)就行了。
问题解答
显然对于每一个子问题，对于石头个数为 \(n\)， \(\texttt {sg(n)=n}\)。
所以 \(SG=\oplus_{i=1}^{n}a_i\)。判断 \(\oplus_{i=1}^{n}a_i 是否为零即可\)
代码
#include<bits/stdc++.h>
using namespace std;
int t, n, a;
signed main(){
scanf("%d", &t);
while (t--) {
scanf ("%d", &n); int ans = 0;
while (n--) scanf("%d", &a), ans ^= a;
if (ans == 0) puts("No"); else puts("Yes");
}
return 0;
}