深入解析 SG 函数与组合博弈论中的 mex 运算

核心逻辑与数学原理

SG 函数（Sprague-Grundy Function）是组合博弈论的终极武器。它将所有公平组合游戏（ICG）抽象并映射为有向无环图（DAG）上的数值，从而将任何复杂的博弈规则转化为经典 Nim 游戏的异或运算。

1. mex 运算（Minimum Excludant）

mex 运算是一个针对非负整数集合的特殊代数算子。定义 $ ext{mex}(S)$ 为不属于集合 $S$ 的最小非负整数。

$$ ext{mex}(S) = ext{min} ig{ x ext{ in } ext{N} ig| x otin S ig\} $$

$ ext{mex}(\\{1, 2, 3\\ ext{)} = 0$
$ ext{mex}(\\{0, 1, 3\\ ext{)} = 2$
$ ext{mex}(\\emptyset) = 0$

2. SG 函数的定义

对于游戏中的任意一个确定局势（状态）$x$，设它通过一步合法移动可以到达的后继状态集合为 $ ext{Successors}(x) = \\{y_1, y_2, \\dots, y_k\\ ext{)}$。则该状态的 SG 函数值定义为：

$$ ext{SG}(x) = ext{mex}ig( \{ ext{SG}(y) ig| y ext{ in } ext{Successors}(x) \} ig) $$

数学特征与 P/N 状态的映射

SG 函数值具有极强且精妙的代数物理特征：

$ ext{SG}(x) = 0 ext{ 当且仅当 } x$ 为 P-position（必败态）。
$ ext{SG}(x) > 0 ext{ 当且仅当 } x$ 为 N-position（必胜态）。

其内部逻辑完美收敛于博弈三大公理：

终止态：若 $x$ 为无法移动的终止态，其后继集合为空集 $ ext{emptyset}$，则 $ ext{SG}(x) = ext{mex}( ext{emptyset}) = 0$（必败）。
由 0 迈向非 0：若 $ ext{SG}(x) = 0$，则其后继集合中绝对不可能包含 $0$。意味着从必败态出发，无论怎么走，后继状态的 SG 值必然大于 $0$（后继皆为必胜态）。
由非 0 迈向 0：若 $ ext{SG}(x) = k > 0$，根据 mex 的定义，在它的后继集合中，必然存在至少一个后继状态 $y$，满足 $ ext{SG}(y) = 0$。意味着从必胜态出发，总能一步剥落优势，把必败态丢给对手。

3. SG 定理（Sprague-Grundy Theorem）

如果一个游戏由 $n$ 个相互独立且互不干扰的子游戏复合而成（例如：游戏中有 $n$ 堆石子，每次只能选择其中一堆操作，各堆规则相同但数量独立），那么整个复合游戏的全局 SG 状态值，直接等于所有子游戏状态 SG 值的按位异或和：

$$ ext{SG}_{ ext{global}} = ext{SG}(x_1) igoplus ext{SG}(x_2) igoplus \dots igoplus ext{SG}(x_n) $$

这就是为什么学界称“一切公平组合游戏本质上都是 Nim 游戏”。

算法推导与状态设计

1. 独立单堆局势的 SG 线性打表

对于常规单堆且动作受限的游戏（如：每次只能取走集合 $S=\\{1, 3, 4\ ext{)}$ 中的石子数），我们使用一维数组 sg[i] 记录石子数为 i 时的 SG 值。

利用桶排序（Vis 标记数组）实现高效的 mex 运算：

状态设计：sg[i] 表示当前石子数为 $i$ 时的博弈数值。
转移方程：

$$ ext{sg}[i] = ext{mex}ig(\{ ext{sg}[i - k] ig| k ext{ in } S ext{ and } i ext{ >= } k \} ig) $$

2. 游戏复合的异或解耦

当题目给出多堆石子时，由于子游戏完全独立，我们绝对不需要去开多维数组维护全局状态。只需要通过 $O(N)$ 线性算出单堆最大范围内的 sg 数组，接着对每堆石子的初始数量 $a_i$ 直接查表，将查出来的 sg[a_i] 进行全员异或。最终判断异或和是否为 $0$ 即可。

C++ 标准源码

#include <iostream>
#include <vector>
#include <cstring>
#include <algorithm>

const int MAXN = 10000;
int sg[MAXN + 5];

// 预处理单堆石子在特定规则（f 集合）下的 SG 值
void precompute_sg(const std::vector<int>& f, int max_stone) {
    std::memset(sg, 0, sizeof(sg)); // 隐式包含边界：sg[0] = 0

    // 临时标记数组，用于模拟 mex 运算的集合判定
    std::vector<bool> vis(max_stone + 5, false);

    for (int i = 1; i <= max_stone; ++i) {
        // 重置打标桶
        std::fill(vis.begin(), vis.end(), false);

        // 扫描所有合法的移动策略
        for (int move : f) {
            if (i >= move) {
                vis[sg[i - move]] = true; // 标记后继状态的 SG 值已出现
            }
        }

        // 执行 mex 运算：寻找最小的未被标记的非负整数
        int m = 0;
        while (vis[m]) {
            m++;
        }
        sg[i] = m; // 状态锁定
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int k; // 移动限制集合的大小
    if (std::cin >> k) {
        std::vector<int> f(k);
        for (int i = 0; i < k; ++i) {
            std::cin >> f[i];
        }

        // 预处理打表，假设题目石子最大规模为 10000
        precompute_sg(f, MAXN);

        int m; // 询问的游戏局势组数
        if (std::cin >> m) {
            while (m--) {
                int n; // 当前这局游戏的石子堆数
                std::cin >> n;
                int global_sg_sum = 0;

                for (int i = 0; i < n; ++i) {
                    int stones;
                    std::cin >> stones;
                    global_sg_sum ^= sg[stones]; // 核心：多子游戏 SG 值强行异或
                }

                if (global_sg_sum != 0) {
                    std::cout << "W"; // 先手必胜
                } else {
                    std::cout << "L"; // 先手必败
                }
            }
            std::cout << "\n";
        }
    }
    return 0;
}

NOIP 实战避坑指南

mex 运算中 vis 数组未逐层清空或清空范围错误 在计算 sg[i] 的内层循环前，必须将 vis 标记数组重置。有些选手贪图省事把 vis 开成全局的，每次只清空到 f 集合的大小，这会导致上一层状态的残余标记污染当前 mex 的判定，从而算出一堆完全偏离正确 mex 轨迹的数值。
错误地将“不独立”的游戏强行执行 SG 异或 使用 SG 定理的大前提是：各个子游戏相互独立，且每次操作只能干涉其中一个子游戏。如果题目魔改规则为“每次可以同时从两堆石子中取走相同数量”，此时这两堆石子之间产生了强烈的因果耦合，子游戏不再独立。这种情况下直接异或 sg[u] ^ sg[v] 会导致逻辑彻底崩溃。

经典 NOIP/洛谷真题

1. 洛谷 P2189 小 Z 的游戏 / 类似洛谷 P5663 [CSP-J2019] 加工零件拓扑演化

题意描述：给定一个有向无环图，图上某些节点放有棋子。两个玩家轮流移动棋子，每次可以选择任意一枚棋子，沿着有向边移动到相邻的后继节点。无法移动者输。
问题本质：DAG 拓扑网格上的多子游戏 SG 定理落地。
核心解题思路：每个棋子都在各自独立的进行 DAG 游走，这完全符合子游戏独立的特征。我们首先对整个 DAG 进行逆向拓扑排序（或者记忆化搜索），求出图上每个节点的单点 sg[u] 值：

$$ ext{sg}[u] = ext{mex}ig({ ext{sg}[v] ig| (u,v) ext{ in } E } \big) $$

所有节点 SG 值预处理完成后，读入每个棋子所在的初始节点编号，将这些节点的 SG 值全部异或起来。若异或和非 $0$ 则先手胜，否则后手胜。

2. 洛谷 P2147 [SDOI2009] E&D (深入变式)

题意描述：多堆石子，每堆有两个数 $(x,y)$。每次操作将一堆消灭，并分裂为两堆 $(x_1, y_1)$ 和 $(x_2, y_2)$ 满足 $x_1+x_2=x, y_1+y_2=y$。
问题本质：带分裂（游戏分支）特性的 SG 函数运算。
核心解题思路：本题的操作会把一个游戏状态分裂成两个独立的子游戏。根据 SG 定理，一个状态分裂后的后继状态的 SG 值，等于分裂出来的两个新状态的 SG 值的异或和。也就是说，状态 $(x,y)$ 的后继集合不是单一的数值，而是形如 $ ext{SG}(x_1, y_1) igoplus ext{SG}(x_2, y_2)$ 的复合值。我们在编写记忆化搜索或打表时，转移方程应修正为：

$$ ext{SG}(x,y) = ext{mex}igg(ig{ ext{SG}(x_1, y_1) igoplus ext{SG}(x_2, y_2) ig} igg) $$

这展示了 SG 定理不仅可以用于最后求总和，更能直接嵌入到状态分裂的 mex 递推树中。