按照自己的学习顺序写的，可能有点奇怪。这是这个系列中唯一有用的东西了。
ICG 游戏
Nim 游戏
有 \(n\) 堆石子，第 \(i\) 堆有 \(a_i\) 个，每次行动可以从任意一堆中取出任意多个（至少一个），两人轮流行动，先不能行动者输。问谁有必胜策略。
在解决具体的问题前，我们首先关注博弈本身的性质。
用 \(x\) 表示一个局面，用一个局面先手必胜，那么 \(P(x)=1\)，否则 \(P(x)=0\)。类似的，后手必胜时有 \(N(x)=1\)，否则 \(N(x)=0\)。我们有 \(P(x)\oplus N(x)=1\)，这里 \(\oplus\) 表示按位异或运算（也记为 \(\operatorname{xor}\)），也就是说一个局面要么先手必胜，要么后手必胜。这个结论的严谨证明将在后面出现。
更进一步，如果一个局面 \(x\) 存在后续局面 \(y\) 有 \(P(y)=1\)，那么 \(P(x)=1\)，否则 \(P(x)=0\)。类似的，如果一个局面 \(x\) 所有后续局面 \(y\) 都有 \(N(y)=1\)，则 \(N(x)=1\)，否则 \(N(x)=0\)。
基于这样基本的理论，我们可以轻易的写出 dp 转移来解决这个问题，不够这样的复杂度是 \(O(V^n)\) 的，其中 \(V\) 表示 \(a_i\) 的最大取值，这样的复杂度是难以接受的。
试着发掘 Nim 游戏本身的性质，下面是两个例子。此处用 \((a_1,a_2,a_3\ldots a_n)\) 表示有 \(n\) 堆石子，第 \(i\) 堆有 \(a_i\) 个的局面。
-
一开始，局面为 \((x,x)\)，那么先手后手只需要模仿先手的操作，局面就总是形如 \((x,x)\)，且该先手操作，易知石子个数单减，于是局面 \((x,x)\) 下后手必胜。如果 \(x\) 表示若干堆石子的状态，不难发现上面的过程依然可以使得后手必胜。
-
一开始，局面为 \((2,3)\)，先手只需从第 \(2\) 堆中取 \(1\) 个，使局面变为 \((2,2)\)，就可以变为上面的情形，故局面 \((2,3)\) 是先手必胜的。
-
一开始，局面为 \((1,2,3)\)，尝试所有可能后可以发现是后手必胜的。
可以用程序验证更大的例子，观察 \((x,y,z)\) 在 \(1\le x\le y\le z\le6\) 的答案（ Previous 表示先手必胜，Next 表示后手必胜 ）：
(1,1,1)=Previous (1,1,2)=Previous (1,1,3)=Previous (1,1,4)=Previous (1,1,5)=Previous (1,1,6)=Previous
(1,2,2)=Previous (1,2,3)=Next (1,2,4)=Previous (1,2,5)=Previous (1,2,6)=Previous
(1,3,3)=Previous (1,3,4)=Previous (1,3,5)=Previous (1,3,6)=Previous
(1,4,4)=Previous (1,4,5)=Next (1,4,6)=Previous
(1,5,5)=Previous (1,5,6)=Previous
(1,6,6)=Previous
(2,2,2)=Previous (2,2,3)=Previous (2,2,4)=Previous (2,2,5)=Previous (2,2,6)=Previous
(2,3,3)=Previous (2,3,4)=Previous (2,3,5)=Previous (2,3,6)=Previous
(2,4,4)=Previous (2,4,5)=Previous (2,4,6)=Next
(2,5,5)=Previous (2,5,6)=Previous
(2,6,6)=Previous
(3,3,3)=Previous (3,3,4)=Previous (3,3,5)=Previous (3,3,6)=Previous
(3,4,4)=Previous (3,4,5)=Previous (3,4,6)=Previous
(3,5,5)=Previous (3,5,6)=Next
(3,6,6)=Previous
(4,4,4)=Previous (4,4,5)=Previous (4,4,6)=Previous
(4,5,5)=Previous (4,5,6)=Previous
(4,6,6)=Previous
(5,5,5)=Previous (5,5,6)=Previous
(5,6,6)=Previous
(6,6,6)=Previous
我们可以猜测先手必胜的条件是 \(a_1\oplus a_2\oplus a_3\oplus \cdots \oplus a_n\ne0\)，考虑证明：
等价的命题是：后手必胜的条件是 \(a_1\oplus a_2\oplus a_3\oplus \cdots \oplus a_n=0\)。下面先给出构造。
我们假设 \(a_1\oplus a_2\oplus a_3\oplus \cdots \oplus a_n=x\)。
由异或的性质可知，一定存在 \(a_k\)，使得 \(\operatorname{highbit}(a_k)=\operatorname{highbit}(x)\)。从第 \(k\) 堆中取出 \(a_k-(a_k\oplus x)\) 个后，第 \(k\) 堆余下 \(a_k\oplus x\) 个，此时有
\[\begin{align*} a_1\oplus a_2\oplus\cdots\oplus a_k^\prime\oplus \cdots\oplus a_n&=a_1\oplus a_2\oplus\cdots\oplus a_k\oplus x\oplus \cdots\oplus a_n\\ &=x\oplus x\\ &=0\\ \end{align*} \]如果当前已经有 \(a_1\oplus a_2\oplus \cdots \oplus a_n=0\)，那么不管先手如何操作，之后都有 \(a_1\oplus a_2\oplus \cdots \oplus a_n\ne0\)，因为对于任意的 \(x\)，有且只有 \(x\) 满足 \(x\oplus x=0\)。
而终止局面 \((0)\) 时显然满足 \(a_1=0\)，且这个局面是后手必胜的。那么通过上文的构造方式就可以使得 \(a_1\oplus a_2\oplus a_3\oplus \cdots \oplus a_n\ne0\) 时先手必胜。
反常 Nim 游戏
Nim 游戏胜负规则相反。
直接上结论了：
满足下列条件之一时先手必胜，否则后手必胜。
- 有偶数堆 \(1\) 个石子的堆。
- 有至少一堆石子个数 \(>1\)，且 \(a_1\oplus a_2\oplus \cdots \oplus a_n\ne0\)。
第一个条件显然，考虑第二个条件：
若只有一堆石子个数 \(>1\)，那么我们可以分奇偶讨论。
- 如果有偶数堆，那么把 \(>1\) 的那堆取完。
- 如果有奇数堆，那么把 \(>1\) 的那堆取到只有 \(1\) 个。
易知此时先手必胜。
若有多堆石子个数 \(>1\)，考虑 \(a_1\oplus a_2\oplus \cdots \oplus a_n=x\)。
- \(x=0\)，考虑可能的转移。
- 拿走一堆使得其余下的个数 \(\le1\)，那么可以转化为先手必胜的情况。
- 否则一定有 \(x^\prime\ne0\)，转化为下面的情况。
- \(x\ne0\)，用 Nim 游戏一样的构造转移到上面的状态。注意到转移时石子个数递减，最终转移一定变成只有一堆石子时先手必胜。
综上可知先手必胜。
SG 函数
到这里，我们终于可以给出 ICG 游戏的定义：
在一个 DAG 上，有一个棋子，两人轮流移动一步（走过一条边），先不能移动者负。
定义 \(\text{SG}(x)\) 函数，其中 \(x\) 是 DAG 上的一个点。
定义 \(\operatorname{SG}(x)=0\) 当 \(x\) 出度为 \(0\)，否则 \(\operatorname{SG}(x)=\operatorname{mex}(\{\operatorname{SG}(v)\mid x\rightarrow v\})\)，即其所有后继的 \(\operatorname{SG}\) 值的 \(\operatorname{mex}\)。
定义 \(\operatorname{mex}(S)\) 表示最小的集合 \(S\) 中未出现过的自然数，比如 \(\operatorname{mex}(1,2,3)=0,\operatorname{mex}(0,1,2,3)=4,\operatorname{mex}(0,1,2,4)=3\)。
如果一个点 \(x\) 满足 \(\operatorname{SG}(x)=0\)，那么在这个点处后手必胜，否则先手必胜。
证明和 Nim 游戏几乎一模一样：终止处 \(\operatorname{SG}(x)=0\)，而 \(\operatorname{SG}(x)>0\) 意味着可以从这个点走到 \(\operatorname{SG}(x)=0\) 的点，于是只需要把 Nim 游戏中的名词替换一下就可以了。
k-SG
更常见的情形是有多个 ICG 游戏同时存在，每次可以选择其中一个操作。
不加证明的，我们给出 \(\operatorname{SG}(x)=\operatorname{SG}(x_1)\oplus \operatorname{SG}(x_2)\oplus \operatorname{SG}(x_3)\oplus\ldots\oplus \operatorname{SG}(x_n)\)。其中 \(x_1,x_2\ldots x_n\) 表示 \(n\) 个子游戏。
证明过程和上面几乎一致，故略去。
策梅洛定理
就是 Nim 游戏里说后面会证的那个东西。
对于一个博弈，如果满足下列条件，那么任何局面要么先手必胜，要么后手必胜。
- 两个玩家轮流操作，他们都足够聪明。
- 下一个局面只和当前局面有关，和谁操作无关。
- 双方都完全了解这个博弈的所有信息。
- 博弈过程中不涉及随机变量，且胜负只由局面唯一决定。
- 终止状态时，一个人赢，另一个人输，且不存在平局。
- 博弈总会停止。
证明其实很简单，从终止局面向初始局面编号为 \(0,1,2\ldots n\)，在第 \(0\) 个局面时的后手如果输了，说明在 \(1\) 个局面时（此时他是先手）他已经必败了，否则他不是足够聪明的。以此类推，用数学归纳法不难得出正整数时任何局面 \(x\) 都满足 \(P(x)\oplus N(x)=1\)。