SG

2huk · 2025-07-11 14:55:08 · 算法·理论

Nim 游戏

公平组合游戏的一般思考方式，是将所有的状态放到 DAG 上，用状态之间的有向边模拟一方的操作。

如最经典的 Nim 游戏。有 n 堆石子，每堆石子的大小分别为 \{a_i\}_i。先后手轮流操作，每次从任意一堆石子中取走任意个石子，不能不取。无法取石子的人输。

在这个问题中，当前所有石堆的石子数量构成的长度为 n 的序列就可以看作一个状态，即 DAG 上的节点。一条可能的边形如 [1,1,4] \to [1,1,3]。

显然初始源点为 [a_1,a_2,\dots,a_n]。我们知道，图上每个节点都有一个属性，表示从这个状态开始游戏，先手会不会赢。考虑用一些方法将每个点的属性都求出来。

显然有以下三个性质：

• 没有后继状态的状态是必败态；
• 后继状态中存在必败状态的状态是必胜状态；
• 后继状态中都是必胜状态的状态是必败状态。

因此可以做一个 DAG 上的 DP。从出度为 0 的点开始，将它们标记为必败，然后存在必败出边的点为必胜，所有出边都为必胜的点为必败。可以在线性复杂度内解决问题。

在 Nim 游戏中，容易发现状态数是 \prod (a_i+1) 即 V^n 级别的。建图并 DP 显然不可取。于是有了下面的解法。

我们断言，\bigoplus_{i=1}^n a_i = 0 的状态为必败态，\bigoplus_{i=1}^n a_i \ne 0 的状态为必胜态。

下面令 s = \bigoplus_{i=1}^n a_i \ne 0。

证明时，考虑将其带入三条性质中：

• 没有后继状态，即 a_1=a_2=\dots=a_n=0 的状态。显然其异或和为 0 且必败。满足第一条性质。

• 考虑构造性证明。我们希望找到一堆石子 $a_i$，让它变成 $a_i \oplus s$。这样新的异或和就是 $0$ 了。 可以这样操作的充要条件是 $a_i \oplus s < a_i$，即操作后这堆石子的数量必须减少。此时需要证明一定存在 $i$ 使得 $a_i \oplus s < a_i$。 因为 $s \ne 0$，所以 $s$ 一定有最高二进制位。令 $\operatorname{highbit}(s) = k$。那么一定存在至少一个 $a_i$ 满足 $2^k \in a_i$。更准确的，存在奇数个 $a_i$ 满足 $2^k \in a_i$。 注意到 $a_i \oplus s$ 是除 $i$ 外其它数的异或和。如果 $a_i$ 是某个满足 $2^k \in a_i$ 的数，那么其他数中一定有偶数个满足存在 $2^k$-位。即 $a_i \oplus s$ 的第 $k$ 位一定为 $0$。 而 $s$ 的 $>k$ 的位一定为 $0$。$s$ 与 $a_i$ 异或后，$>k$ 的位都会与 $a_i$ 相同。 也就是说，$a_i \oplus s$ 与 $a_i$ 在 $>k$ 的位都相同，且 $a_i \oplus s$ 的第 $k$ 位是 $0$，$a_i$ 的第 $k$ 位为 $1$。所以 $a_i \oplus s < a_i
• 反证法。当前 $s=0$，一步操作后仍然 $s=0$。设我们操作第 $i$ 堆石子，并将 $a_i \to a_i \oplus k$，那么需要保证 $a_i \oplus k < a_i$。 而已知 $s=0$ 而且 $s \oplus k = 0$（即操作前后异或和都为 $0$），所以 $k=0$。那么这一步操作中并没有取石子，矛盾。

由此引出 SG 定理。

SG 定理

仍然考虑有向图上的博弈。上一节我们给了每个点一个 bool 属性表示是否先手必胜。现在我们将这个属性扩展至非负整数集，即 \operatorname{SG}(u)。

设 \operatorname{next}(u) 表示节点 u 的所有后继状态的集合。则：

显然 \operatorname{SG}(u) 是否为 0 可以说明一个节点的胜负状态。

如果当前游戏是若干个游戏的和，即有多个有向图，每个有向图都有恰好一个起点。最初这些起点上各有一枚棋子，双方轮流操作，选择一个棋子沿着某条出边移动一步。所有棋子都无法移动时后手败。

SG 定理：在这个组合游戏中，先手必胜的充要条件是 \bigoplus\operatorname{SG}(s_i) \ne 0，其中 s_i 表示各个起点。这与 Nim 游戏是极像的。

考虑证明。

因为 \operatorname{SG}(u)=0 的节点是必败态，因此双方的目标都是让对方走到某个 0 的状态。

由定义易得，\operatorname{SG} 为 x 的点，一定存在 \operatorname{SG} 为 0,1,\dots,x-1 的后继状态。因此可以一步走到这些位置。

事实上，这个点的后继也可能存在 >x 的。但是如果走到这些点，对方可以通过一次操作回到 x。这是没有意义的。

因此问题变成了，从 \operatorname{SG}(s_i) 开始，双方轮流操作，每次走到一个严格小于当前的数，变为 0 时后手赢。这就是 Nim 游戏。求所有起点的 \operatorname{SG} 的异或和即可。