\(\rm NOIP\) 模拟赛考了 \(\rm SG\) 函数，于是来贺一发 oi-wiki
Part 1：公平组合游戏 \(\rm ICG\)
若一个游戏满足：
-
由两名玩家交替行动
-
在游戏进程的任意时刻，可以执行的合法行动与轮到哪名玩家无关
-
不能行动的玩家判负
则称该游戏为一个公平组合游戏
经典的公平组合游戏有很多，包括取数游戏，\(\rm 31\) 点，以及 \(\rm NIM\) 游戏等。
博弈图和状态
如果将每个状态视为一个节点，再从每个状态向它的后继状态连边，我们就可以得到一个博弈状态图。
定义必胜状态为先手必胜的状态，必败状态为*先手必败的状态**。
通过推理，我们可以得出下面三条定理：
- 没有后继状态的状态是必败状态。
- 一个状态是必胜状态当且仅当存在至少一个必败状态为它的后继状态。
- 一个状态是必败状态当且仅当它的所有后继状态均为必胜状态。
如果博弈图是一个有向无环图，则通过这三个定理，我们可以在绘出博弈图的情况下用 \(O(n+m)\) 的时间（其中 \(n\) 为状态种数，\(m\) 为边数）得出每个状态是必胜状态还是必败状态。
\(\rm NIM\) 游戏
地上有 \(n\) 堆石子，第 \(i\) 堆石子有 \(a_i\) 个。两名玩家轮流行动，每人每次可从任意一堆石子里取出任意多枚石子扔掉，可以取完，不能不取。每次只能从一堆里取。最后没石子可取的人就输了。问先手能否必胜
定理
\(\rm NIM\) 游戏先手必胜，当且仅当 \(a_1⊕a_2⊕\dots⊕a_n\ne 0\)
证明：为了证明该定理，只需要证明下面三个定理：
- 定理 1：没有后继状态的状态是必败状态。
- 定理 2：对于 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n \neq 0\) 的局面，一定存在某种移动使得 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0\)。
- 定理 3：对于 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0\) 的局面，一定不存在某种移动使得 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0\)。
对于定理 1，没有后继状态的状态只有一个，即全 \(0\) 局面。此时 \(a_1 \oplus a_2 \oplus \ldots \oplus a_n = 0\)。
对于定理 2，不妨假设 \(a_1 \oplus a_2 \oplus \ldots a_n = k \neq 0\)。如果我们要将 \(a_i\) 改为 \(a_i'\)，则 \(a_i'=a_i \oplus k\)。容易证明存在这样的 \(a_i\) 使得 \(a_i'<a_i\)
对于定理 3，如果我们要将 \(a_i\) 改为 \(a_i'\)，则根据异或运算律可以得出
\(a_i=a_i'\)，因而这不是个合法的移动。
Part 2：有向图游戏与 \(\rm SG\) 函数
在一个有向无环图中，只有一个起点，上面有一个棋子，两个玩家轮流沿着有向边推动棋子，不能走的玩家判负。该游戏被称为有向图游戏
大部分的公平组合游戏都可以转换为有向图游戏。具体方法是，把每个局面看成图中的一个节点，并且从每个局面沿着合法行动能够到达的下一个局面连有向边
\(\rm Mex\) 运算
设 \(S\) 表示一个非负整数集合。定义 \(\operatorname{mex}(S)\) 函数的值为不属于集合 \(S\) 中的最小非负整数，即：
\[\text{mex}(S)=\min\limits_{x\in \mathbb{N},x\not\in S}\{x\} \]\(\rm SG\) 函数
在有向图游戏中，对于每个节点 \(x\)，设从 \(x\) 出发共有 \(k\) 条有向边，分别到达节点 \(y_1,y_2,\dots,y_k\)，定义 \(\rm SG(x)\) 为 \(x\) 的后继节点 \(y_1,y_2,\dots,y_k\) 的 \(\rm SG\) 函数值构成的集合再执行 \(\rm mex\) 运算的结果，即：
\[\text{SG}(x)=\text{mex}(\{\text{SG}(y_1),\text{SG}(y_2),\dots,\text{SG}(y_k)\}) \]特别地，整个有向图游戏 \(G\) 的 \(\rm SG\) 函数值被定义为有向图游戏起点 \(s\) 的 \(\rm SG\) 函数值，即 \(\text{SG}(G)=\text{SG}(s)\)
有向图游戏的和
设 \(G_1,G_2,\dots,G_m\) 是 \(m\) 个有向图游戏。定义组合游戏 \(G\)，它的行动规则是任选某个有向图游戏 \(G_i\)，并在 \(G_i\) 上行动一步。\(G\) 被称为有向图游戏 \(G_1,G_2,\dots,G_m\) 的和。
有向图游戏的和的 \(\rm SG\) 函数值等于包含它的各个子游戏的 \(\rm SG\) 函数值的异或和，即：
\[\text{SG}(G)=\operatorname{SG}(G_1) \oplus \operatorname{SG}(G_2) \oplus \ldots \oplus \operatorname{SG}(G_m) \]定理
-
有向图游戏的某个局面必胜，当且仅当该局面对应节点的 \(\rm SG\) 函数值大于 \(0\)
-
有向图游戏的某个局面必败，当且仅当该局面对应节点的 \(\rm SG\) 函数值等于 \(0\)