$Nim$游戏

给定 $n$ 堆石子，两位玩家轮流操作，每次操作可以从任意一堆石子中拿走任意数量的石子（可以拿完，但不能不拿），最后无法进行操作的人视为失败。

问如果两人都采用最优策略，先手是否必胜。

输入格式

第一行包含整数 $n$。

第二行包含 $n$ 个数字，其中第 $i$ 个数字表示第 $i$ 堆石子的数量。

输出格式

如果先手方必胜，则输出 Yes。

否则，输出 No。

数据范围

$1\le n\le 10^5$，$1\le 每堆石子数\le 10^9$

输入样例：

2
2 3

输出样例：

Yes

题解

$Nim$游戏是个挺古老的游戏，但是它的游戏解在$19$世纪才被发现，所以如果没自己想出来也没关系的😏($doge.$)​​

首先需了解一个位运算：$Xor$运算（异或运算），其数学符号为$\oplus$。其中$aXorb$被定义为$a,b$相异则为真，$a,b$相同则为假。它除了交换律，结合律外，还有一些神奇的性质：

• **自身为自身的逆运算：**即对于任何两个布尔变量或者数有$(a\oplus b)\oplus b=a$，可以依据这个写出swap(int a, int b)函数：a = a ^ b; b = a ^ b; a = a ^ b，（当然和本题没关系）。

• **满足消去律：**即由$a\oplus c=b\oplus c$可以推出$a=b$。

然后了解一下游戏中两个状态：

• 必胜状态：先手进行某个操作时，留给了后手了一个必败状态，即先手可以走到某一个必败状态
• 必败状态：先手无论如何操作，留给后手的都是必胜状态，即先手走不到任何一个必败状态

注：本文中的“走到一个状态”是指当前$A$走完后，对于$B$的状态

对于形如$Nim$这类博弈问题最重要的是寻找必败态，对于这个必败态，其严格定义如下：

• 无法进行任何移动的局面是必败态：如果一个玩家在当前状态下没有任何合法的移动可以做，那么这个状态就是必败态。
• 可以移动到必败态的局面是非必败态：如果一个玩家能够通过一次合法的移动将游戏状态变为对手的必败态，则该玩家处于非必败态。
• 在必败态做的所有操作的结果都是非必败态：处于必败态的一方，无论做出怎样的合法移动，都会导致自己仍然处于不利的状态。

结论：

对于普遍$Nim$游戏问题，假设有$n$堆石头，石子的数目分别是$a_1,a_2,...,a_n$，如果$a_1\oplus a_2\oplus ...\oplus a_n\ne 0$，先手必胜；反之，先手必败。

证明该结论的过程，即为证明其满足以上三个必败态的三条性质即可。

证明($Bouto{n}^{\prime }sTheorem$)：

• 操作到最后，即无法再进行任何移动时，每堆的石子数都为$0$，即：
  $$a_1\oplus a_2\oplus ...\oplus a_n=0$$

• 对于第二个可移动到必败局的局面是非必败态，即为：如果对于某个局面$a_1\oplus a_2\oplus ...\oplus a_n=x\ne 0$，一定存在某个合法的移动，使得$a_i$变为$a_i^{\prime }$后，$a_1\oplus a_2\oplus ...\oplus a_i^{\prime }\oplus ...\oplus a_n=0$。

**证明：**不妨设$x$的二进制表示中最高一位$1$在第$k$位，则存在$a_i$的二进制表示在$x$的最高位上的$1$（否则$x$的最高位的$1$从何得到）。这时$a_i\oplus x<a_i$，不妨从第$i$堆石子中拿走$(a_i-a_i\oplus x)$个石头，即$a_i^{\prime }=a_i\oplus x$，此时：
$$a_1\oplus a_2\oplus ...\oplus a_i^{\prime }...\oplus a_n=x\oplus x=0$$

• 对于第三个在必败态做的所有操作的结果都是非必败态，即为：对于某个局面$a_1\oplus a_2\oplus ...\oplus a_n=0$，一定不存在某个合法的移动，使得$a_i$变为$a_i^{\prime }$后，$a_1\oplus a_2\oplus ...\oplus a_i^{\prime }\oplus ...\oplus a_n=x\ne 0$。

**反证法：**因为异或运算满足消去率，若$a_i$变为$a_i^{\prime }$后，运算得出$x=0$：
$$a_1\oplus a_2\oplus ...\oplus a_i...\oplus a_n=a_1\oplus a_2\oplus ...\oplus a_i^{\prime }...\oplus a_n$$
则$a_i=a_i^{\prime }$，所以将$a_i$移动为$a_i^{\prime }$是非法的，证毕。

基于对三个必败态的证明：

• 如果先手面对的局面是$a_1\oplus a_2\oplus ...\oplus a_n=x\ne 0$，那么先手总可以拿走一堆若干个石子，将局面变为$a_1\oplus a_2\oplus ...\oplus a_n=0$，如此重复，最后一定是后手面临最终没有石子可拿的状态，先手必胜。
• 先手必败同理。

#include<iostream>
using namespace std;int main()
{int n;cin >> n;int res = 0;while (n -- ){int x;cin >> x;res ^= x;}if(!res) cout << "No" << endl;else cout << "Yes" << endl;return 0;
}

如果将$Nim$游戏的规则改变，如：

有$n$堆石子，每次可以从第$1$堆中取$1,2$或$3$个石子，可以从第$2$堆中取奇数个石子，可以从第$3$堆及以后石子里取任意颗……

此时只知道异或运算暂时还无法应付该情况，所以还需了解一些其他道具。

---

SG函数

平等组合游戏$(ICG)$：一种两人轮流进行的、完全信息的、无运气因素的组合游戏，并且游戏中双方的可选行动和胜负条件完全对称，即对两位玩家没有偏向性。在这种游戏中，游戏的状态和操作规则都是公开的，双方都知道所有可能的走法，且没有隐藏信息或随机性。

1. 两个人进行博弈

2. 两人轮流进行决策且做出的决策都对自己有利

3. 游戏中同一个局势不能多次到达且游戏不能有平局

4. 当有人无法做出决策时游戏结束，无法做出决策的人输

5. 游戏可以在有限步数内结束

6. 任意游戏者在某一局势时能做出决策的集合只与当前局势有关，与游戏者本身无关

必胜态与必败态：定义$P-position,N-position$：

• $P-position$：必败态(简称$P$)，即在决策前就处于这种状态的人必败
• $N-position$：必胜态(简称$N$)，即在决策前就处于这种状态的人必胜

如果更严谨的定义$P$与$N$，则：

• 无法移动的状态为$P$，（或为$Terminal-position$）

• 可以移动到$P$的状态为$N$

• 任意移动都会到$N$的状态为$P$

组合游戏中的$DAG$​图：如果我们将每一种状态向它能到达的状态连边，那么一个组合游戏的所有状态就能组成一个$DAG$(有向无环图):

给出一张DAG，在给定起点处有一枚棋子，两人轮流移动棋子，如果谁不能移动了就判输。

也就是说，任何一个$ICG$都可以通过把每个局面看成一个顶点，对每个局面和它的子局面连一条有向边来抽象成这个“有向图游戏”。

$SG$函数是人们在研究博弈问题上迈出的一大步，人们不再一味的通过找规律来得到博弈结论，而是将博弈问题的每一个状态进行量化分析并总结出了某些普遍性的规律。

SG函数及SG定理

给出一张DAG，在给定起点处有一枚棋子，两人轮流移动棋子，如果谁不能移动了就判输。

这个游戏可以认为是所有$ICG$的抽象模型。

下面我们在有向无环图的顶点定义**$Sprague-Garundy$函数**。首先定义**$mex$运算**，表示集合中最小的未出现的自然数，如： m e x { 1 , 2 , 3 } = 0 , m e x { 0 , 2 , 3 } = 1 mex\lbrace 1,2,3 \rbrace=0,mex\lbrace 0,2,3\rbrace=1 mex{1,2,3}=0,mex{0,2,3}=1。

对于给定一个的有向无环图中，定义关于图的每个顶点的$Sprague-Garundy$函数为：
S G ( x ) = m e x { g ( y ) ∣ y 为 x 的后继 } = m e x ( { S G ( y 1 ) , S G ( y 2 ) , . . . , S G ( y k ) } ) SG(x)=mex\lbrace g(y)|y为x的后继\rbrace=mex(\lbrace SG(y_1),SG(y_2),...,SG(y_k)\rbrace) SG(x)=mex{g(y)∣y为x的后继}=mex({SG(y1​),SG(y2​),...,SG(yk​)})
$SG$函数描述的是博弈中某个状态量化后的值。其有以下性质：

• 终止状态$SG$值为$0$，因为它没有出边(即可到达的状态)：即所有$Terminal-position$所对应的顶点，也就是没有出边的顶点，其后续集合为空集，所以$SG$值为$0$
• $SG$值为$0$的状态为必败态，它的后继状态$SG$值都不为$0$，满足必败态定义：对于一个$SG(x)=0$顶点$x$，其所有的后续$y$都满足$SG(y)\ne 0$
• $SG$值不为$0$的状态为必胜态，它的后继状态$SG$值有为$0$的状态，满足必胜态定义：对于一个$SG(x)\ne 0$顶点$x$，必定存在一个后续$y$满足$SG(y)=0$

不妨再考虑以下顶点的$SG$值的意义：

当$SG(x)=k$时，表明对于任意一个$0⩽i<k$，都存在$x$的一个后继$y$满足$SG(y)=i$，也就是说当某个棋子的$SG$值是$k$时，我们可以转换成任意的$i$，但绝不能保持$k$不变。同时，在$Nim$游戏中，每次都必须选择拿走石子，而不能保持$k$不变。这表明，如果将$n$枚棋子所在的顶点的$SG$值看作$n$堆相应数量的石子，那么这个$Nim$游戏的每个必胜策略都对应于原来的这$n$枚棋子的必胜策略。

对于$n$个棋子，设它们对应的顶点的$SG$值为$a_1,a_2,...,a_n$，再设局面$a_1,a_2,...,a_n$时的$Nim$游戏的一种必胜策略是将$a_i$变为$k$，那么原游戏中的一种必胜策略就是把第$i$枚棋子移动到一个$SG$值为$k$的顶点。

接下来证明这种多棋子的有向图游戏的局面是$P-position$当且仅当所有棋子所在的位置的$SG$函数的异或和（$Num$和）为$0$即可。该证明与$Nim$游戏中证明必胜策略($Bouto{n}^{\prime }sTheorem$)差不多相同。

注：如果$n$枚棋子不是在一个有向图上，而是每个棋子都在一个有向图上，每次可以任选一个棋子进行移动，这样并不会给结论带来任何变化。

定义有向图游戏的和：设$G_1,G_2,...,G_n$是$n$个有向图游戏，定义游戏$G$是$G_1,G_2,...,G_n$的和，游戏$G$的移动规则是：任选择一个子游戏$G_i$并移动上面的棋子。则$SG(G)=SG(G_1)\oplus SG(G_2)\oplus ...\oplus SG(G_n)$，即游戏的和的$SG$值为其所有子游戏的$SG$函数值的异或和。

那么一个局面为先手必败当且仅当该局面的$SG$值为$0$。同样如果游戏的和为$0$，那么先手必败。

证明(SG)：

所有终止状态的$SG$值都是$0$，每次如果先手使本来$SG$值异或和为$0$的局面异或和改变为$k$，那么后手就一定能找到一个单一游戏使它的$SG$值从$SG(x)$变成$SG(x)\oplus k$。因为$SG(x)\oplus k<SG(x)$，而$x$的后继状态一定有一个状态的$SG$值为比它小的$SG(x)\oplus k$。

之前有提到，任何一个$ICG$都可以抽象成一个有向图游戏。所以$SG$函数和游戏的和的概念就可以用于不止有向图游戏中了。我们给每个$ICG$的每个局面定义$SG$值，以及$n$个$ICG$的和。当面对由$n$个游戏组成的一个游戏是，只需对于每个游戏找出求它的每个局面的$SG$值的方法即可。

而如何求解$SG$函数，根据定义可知：依次枚举每种状态并枚举每种状态能到达的状态，找到每个状态后继状态$SG$值中没有出现的最小自然数就是它的$SG$值。

综上：知道$SG$函数和游戏的和后，我们就可以把复杂的游戏分解成若干个子游戏，对于每个子游戏找出它的$SG$函数，然后全部异或和得到原游戏的$SG$函数​，​就可以​优雅​地​解决​原游戏了😎。​

---

回到游戏规则改变后的$Nim$问题：

有$n$堆石子，每次可以从第$1$堆中取$1,2$或$3$个石子，可以从第$2$堆中取奇数个石子，可以从第$3$堆及以后石子里取任意颗……

题解：

• 我们可以将其看作三个子游戏

• 第一个游戏：只有一个堆，每次取出$1,2$或$3$个石子：

  • $$\begin{gathered} 状态0的SG值为0(无石子) \\ 状态1的SG值为1(取1石子) \\ 状态2的SG值为2(取2石子) \\ 状态3的SG值为3(取3石子) \\ 状态4的SG值回到0，因为取1,2,3可以回到之前已有状态 \end{gathered}$$

  • 易得：$x$个石子的$SG$值为$x\mathrm{mod}4$

• 第二个游戏：只有一个堆，每次取出奇数个石子：

  • $$\begin{gathered} 状态0的SG值为0 \\ 状态1的SG值为1(取1个石子) \\ 状态2的SG值为0(只能取奇数个，剩1后变成已知SG值的状态) \\ 状态3的SG值为1(取1个石子到状态2，或取3个到状态0) \end{gathered}$$

  • $x$个石子的$SG$值为$x\mathrm{mod}2$

• 第三个游戏即为普通$Nim$游戏了

根据$SG$定理可得:
$$S{G}_{total}=SG(G_1)\oplus SG(G_2)\oplus \left[SG(G_3)\oplus ...\oplus SG(G_n)\right]$$
当$S{G}_{total}=0$，当前局面为必败局，反之为必胜局。

---

$anti-SG$与$SJ$定理

两个顶尖聪明的人在玩游戏，有$n$堆石子，第$i$堆有$a_i$个，每人每次能从一堆石子中取任意多个石子但不能不取，取到最后一个的人输，请问先手与后手谁必胜？

相较于普遍$Nim$游戏来说，变为了无法操作的人获胜，而进行最后一个操作的人失败。

经过分析，我们发现先手必胜有两种情况：

• 每堆石子数异或和不为$0$且至少有一堆石子数大于$1$

• 每堆石子数异或和为$0$且每堆石子只有$1$个

证明：

• 由于异或和不为$0$，根据$Nim$游戏的性质，先手一定能通过操作使得异或和变为$0$，所以异或和不为$0$表示局面不是必败态，因此先手有至少一种操作可以确保自己不是最后一个取石子的人。

  • 如果所有堆的石子数都变为$1$，则后手必败（因为没有石子可取）。

• 如果仍有堆的石子数大于$1$，则先手可以继续保持异或和为$0$的状态，将局面交还给对手。

  由于每次取石子总数递减，游戏最终会走到只剩最后一颗石子的局面。此时，后手被迫取走最后一颗石子，因而输掉游戏。因此，在这种情况下，先手可以通过控制局面变化来保证自己不会是最后一个取石子的人，从而获得胜利。

  **具体操作：**我们先除去偶数堆石子数为$1$的石子堆(因为这些一定是轮番取完且不改变先后手关系)，先手只要第一次取石子使剩下石子堆异或和为$0$，之后每次只要后手改变异或值就将异或值再取为$0$，到最后一定会剩下两堆同样多数目且数目都大于$1$的石子，假设每一堆剩下$1+x$个石子($x>0$)，这时后手先取：

  • 如果后手将一堆全取走，那么先手将另一堆取$x$个即可，这时只剩下$1$个；

  • 如果后手使一堆剩下$1$个，那么先手将另一堆全取走即可，这时只剩下$1$个；

  • 如果后手使一堆剩下大于$1$个，那么先手在另一堆取同样多个，局势又变成了剩下两堆$1+x$个石子的情况。

• 当所有堆的石子数的异或和为 $0$时，通常表示当前局面为一个“必败态”，即如果对方不犯错误，当前玩家将无法获胜。

  然而，在这种特殊情况下，当每堆只有 $1$ 个石子，且异或和为 $0$，意味着所有的石子数都为 $1$ 且总数为偶数（异或和为 $0$ 表示奇偶平衡）。这种局面下，先手可以通过取走一颗石子，将剩下的石子数变为奇数个。此后，先手每次可以模仿后手的操作，以确保自己总是留下偶数个石子给对方，直到最终后手被迫拿走最后一颗石子而输掉比赛。

  因此，当异或和为 $0$ 且每堆石子数为 $1$ 时，先手可以通过这样策略性的操作确保后手取走最后一颗石子，从而获胜。

• 综上：这两种情况之所以是先手必胜的关键原因在于：

  1. 异或和不为 0 且至少一堆石子数大于 1：先手可以通过操作将局面转变为对后手不利的状态，避免自己成为最后一个取石子的人。
  2. 异或和为 0 且每堆石子数为 1：先手可以控制局面，通过对称策略迫使后手成为最后一个取石子的人。

类似于$SG$定理，同样也有$SJ$定理：

对于$anti-SG$游戏，先手必胜当且仅当：

1. 游戏的和不为$0$且至少有一个单一游戏的$SG$函数大于$1$

2. 游戏的和为$0$且所有单一游戏的$SG$函数不大于$1$

证明和$anti-Nim$的证明相同，只不过对于第二种情况一个$SG$函数为$1$的局势可以变成$SG$函数大于$1$的局势，只要将这种情况转为第一种情况就好了。

---

multi-SG

有$n$堆石子，两个人可以从任意一堆石子中拿任意多个石子(不能不拿)或把一堆数量不少于$2$的石子分为两堆不为空的石子。

规定没法拿的人失败，问谁会胜利？

不妨计算过一下前几个状态的$SG$值：
s g ( 1 ) = m e x { s g ( 0 ) } s g ( 2 ) = m e x { s g ( 0 ) , s g ( 1 ) } = 2 s g ( 3 ) = m e x { s g ( 0 ) , s g ( 1 ) , s g ( 2 ) , s g ( 1 , 2 ) } = 4 s g ( 4 ) = m e x { s g ( 0 ) , s g ( 1 ) , s g ( 2 ) , s g ( 1 , 3 ) , s g ( 2 , 2 ) , s g ( 3 ) } = 3 sg(1) = mex\{sg(0)\}\\ sg(2) = mex\{sg(0), sg(1)\} = 2\\ sg(3) = mex\{sg(0), sg(1), sg(2), sg(1,2)\} = 4\\ sg(4) = mex\{sg(0),sg(1), sg(2), sg(1,3), sg(2,2), sg(3)\} = 3 \\ sg(1)=mex{sg(0)}sg(2)=mex{sg(0),sg(1)}=2sg(3)=mex{sg(0),sg(1),sg(2),sg(1,2)}=4sg(4)=mex{sg(0),sg(1),sg(2),sg(1,3),sg(2,2),sg(3)}=3
综上可得：
$$SG(x)=\{\begin{array}{ll}x-1& (x\mathrm{mod}4=0)\\ x& (x\mathrm{mod}4=1\vee 2)\\ x+1& (x\mathrm{mod}4=3)\end{array}$$

---

every-SG

$every-SG$游戏规定对于任意未结束的单一游戏，游戏者必须对它进行决策，游戏结束时间决定于最后一个结束的单一游戏，胜负则取决于最后一个结束的单一游戏的输赢。

对于每一步决策，因为一直$SG$值为$0$时必败，$SG$值不为$0$时必胜，所以我们一定希望$SG$为$0$的局势尽快结束，$SG$不为$0$的局势尽量慢点结束。

所以需要知道$SG$值为$0$的局势最少多少步结束，$SG$值不为$0$的局势最多多少步结束。

我们用$step$函数来记录这个值：
s t e p ( u ) = { 0 , u为终止状态 max ⁡ { s t e p ( v ) } , s g ( u ) ≠ 0 ∧ v 为 u 的后继 ∧ s g ( v ) = 0 min ⁡ { s t e p ( v ) } , s g ( u ) = 0 ∧ v 为 u 的后继 step(u) = \begin{cases} 0, & \text{u为终止状态} \\ \max\{step(v)\}, & sg(u) \neq 0 \land v为u的后继 \land sg(v) = 0 \\ \min\{step(v)\}, & sg(u) = 0 \land v为u的后继 \end{cases} step(u)=⎩ ⎨ ⎧​0,max{step(v)},min{step(v)},​u为终止状态sg(u)=0∧v为u的后继∧sg(v)=0sg(u)=0∧v为u的后继​
对于every-SG游戏先手必胜当且仅当单一游戏step最大的一个为奇数。