在算法竞赛中，博弈论问题通常涉及到两名玩家轮流操作。要理解复杂的博弈模型，通常从最基础、最经典的 Nim 游戏 开始。

Nim 游戏

Nim 游戏是博弈论中最基础的模型。

游戏规则

有 \(n\) 堆石子，第 \(i\) 堆石子数为 \(a_i\)。两名玩家轮流从任意一堆中取走任意数量的石子（至少取一个，至多取完该堆），最后取光石子的人获胜。

Nim 和

Nim 游戏的胜负由所有堆石子数的异或和（称为 Nim 和）决定：\(S = a_1 \oplus a_2 \oplus \cdots \oplus a_n\)。

• 若 \(S \ne 0\)，当前状态为必胜态，先手总能通过一次操作将 \(S\) 变为 0。
• 若 \(S = 0\)，当前状态为必败态。无论先手如何操作，产生的 \(S'\) 必定不为 0。

证明

1. 终局状态：当所有 \(a_i = 0\) 时，游戏结束，此时 \(S = 0 \oplus 0 \oplus \cdots \oplus 0 = 0\)，这符合必败态的定义。
2. \(S \neq 0 \Rightarrow S = 0\) 的转移：设 \(S\) 的二进制表示中最高位的 1 在第 \(k\) 位，那么至少存在一堆石子 \(a_i\)，其第 \(k\) 位也是 1。显然 \(a_i \oplus S \lt a_i\)，因为异或 \(S\) 之后，\(a_i\) 的第 \(k\) 位变成了 0，而更高的位没变。将第 \(i\) 堆石子数从 \(a_i\) 减少到 \(a_i' = a_i \oplus S\)，新的异或和为 \(S' = S \oplus a_i \oplus (a_i \oplus S) = S \oplus S = 0\)。
3. \(S = 0 \Rightarrow S \neq 0\) 的转移：若从第 \(i\) 堆取走一些石子，使其从 \(a_i\) 变为 \(a_i' \ (a_i' \lt a_i)\)。新的异或和 \(S' = S \oplus a_i \oplus a_i' = 0 \oplus a_i \oplus a_i' = a_i \oplus a_i'\)，由于 \(a_i \ne a_i'\)，故 \(S' \ne 0\)。

例题：P2197 【模板】Nim 游戏

#include <cstdio>
int main()
{
    int t; scanf("%d", &t);
    while (t--) {
        int n; scanf("%d", &n);
        int res = 0;
        for (int i = 0; i < n; i++) {
            int x; scanf("%d", &x);
            res ^= x;
        }
        if (res != 0) printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}

习题：P4301 [CQOI2013] 新Nim游戏

本题是传统 Nim 游戏的变种，设有 \(k \ (1 \le k \le 100)\) 堆火柴，每堆火柴的数量分别为 \(a_i \ (1 \le a_i \le 10^9)\)，规则如下：

1. 第一回合：先手（A）可以拿走若干整堆火柴，接着后手（B）也可以拿走若干整堆火柴。注意：第一回合双方拿走的都是“整堆”，且不能把火柴全部拿完。
2. 后续回合：从先手（A）开始，按照传统 Nim 游戏规则进行（每次从一堆中拿走至少一根火柴，拿走最后一根的人获胜）。

目标：作为先手，求在保证必胜的情况下，第一回合拿走的火柴数量的最小值。

#include <cstdio>
#include <algorithm>
#include <functional>
using namespace std;
using ll = long long;
const int N = 105;
int a[N], d[30];
// 线性基插入函数
bool insert(int x) {
    for (int i = 29; i >= 0; i--) {
        if (!((x >> i) & 1)) continue;
        if (!d[i]) {
            d[i] = x;
            return true;
        }
        x ^= d[i];
    }
    return false;
}
int main()
{
    int k; scanf("%d", &k);
    ll sum = 0;
    for (int i = 0; i < k; i++) {
        scanf("%d", &a[i]);
        sum += a[i];
    }
    // 贪心策略：按火柴数从大到小排序，尽量保留大的火柴堆
    sort(a, a + k, greater<int>());
    ll keep = 0;
    for (int i = 0; i < k; i++) {
        // 如果当前堆与已保留的堆线性无关，则将其保留
        if (insert(a[i])) keep += a[i];
    }
    // 结果为总数减去保留的数量
    printf("%lld\n", sum - keep);
    return 0;
}

变体：阶梯 Nim 博弈

游戏规则

有一个 \(n\) 层的阶梯，每层阶梯上放着若干个硬币。玩家轮流操作，每次可以从第 \(i\) 层阶梯（\(i \ge 1\)）中取走任意数量的硬币，并将它们放到第 \(i-1\) 层，而降落到第 0 层（地面）的硬币就不能再移动了。最后一个移动硬币的玩家获胜，即无法移动者输。

结论与博弈策略

阶梯 Nim 博弈的核心结论是这个游戏等价于只对“奇数层”阶梯上的硬币做经典 Nim 游戏。

设第 \(i\) 层解题的硬币数量为 \(a_i\)，当且仅当所有奇数层硬币数量的异或和为 0 时，当前玩家处于必败态。而只要上述异或和不为 0，当前玩家就有必胜策略。

为什么偶数层不影响胜负？

困惑的地方在于既然可以移动偶数层的硬币，为什么它们不计入异或和？

这其实是一种“对抗策略”：如果对手移动奇数层，这就变成了经典 Nim，只需要根据 Nim 的策略调整另一个奇数层（或该层），使奇数层的异或和重新变回 0；如果对手移动偶数层，例如从第 2 层移到第 1 层，此时奇数层（第 1 层）的硬币增加了，作为应对，只需要立即将对手刚才移到第 1 层的那些硬币，全部再移到第 0 层，那么奇数层（第 1 层）的硬币数恢复原样，异或和不变，由于硬币最终都会掉进第 0 层（终点），这种“搬运”不可能无限进行，所以移动偶数层永远无法改变奇数层的博弈局面。

习题：P10507 Georgia and Bob

在无限长的棋盘上有 \(n \ (n \le 1000)\) 个棋子，两名玩家轮流将一枚棋子向左移动至少一格，但不能逾越其他棋子，也不能重合，无法操作的玩家输。给定棋子的初始位置 \(P_i \ (P_i \le 10000)\)，判断先手是否必胜。

#include <cstdio>
#include <algorithm>
using namespace std;
const int N = 1005;
int p[N], g[N];
void solve() {
    int n; scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", &p[i]);
    sort(p, p + n);
    // 计算间距（从右往左）
    for (int i = n - 1; i > 0; i--) {
        g[n - i - 1] = p[i] - p[i - 1] - 1;
    }
    g[n - 1] = p[0] - 1;
    // 对奇数位间距求异或和 (索引 0, 2, 4...)
    int sum = 0;
    for (int i = 0; i < n; i += 2) {
        sum ^= g[i];
    }
    if (sum > 0) printf("Georgia will win\n");
    else printf("Bob will win\n");
}
int main()
{
    int t; scanf("%d", &t);
    while (t--) solve();
    return 0;
}

公平组合游戏

Nim 游戏属于一类被称为 公平组合游戏（Impartial Combinatorial Games） 的博弈，其特征如下：

1. 有两名玩家，轮流进行操作。
2. 在游戏的任意时刻，合法操作集合仅取决于当前的状态，而与当前轮到哪位玩家无关。
3. 游戏在有限步内结束，且不存在平局。
4. 遵循常规操作原则：最后一名进行合法操作的玩家获胜（即无法移动者输）。

mex 函数与 SG 函数

mex 函数（Minimum Excluded value）

\(\text{mex}(S)\) 定义为集合 \(S\) 中未出现的最小非负整数，如 \(\text{mex}(\{0, 1, 2, 4\}) = 3, \ \text{mex}(\{1, 3, 5\}) = 0\)。

SG 函数

对于一个状态 \(u\)，设其后继状态集合为 \(V = \{v_1, v_2, \dots, v_k\}\)，则状态 \(u\) 的 SG 值定义为 \(\text{SG}(u) = \text{mex}(\{\text{SG}(v_1), \text{SG}(v_2), \dots, \text{SG}(v_k)\})\)。

\(\text{SG}(u) = 0\) 表示该状态为必败态，\(\text{SG}(u) \ne 0\) 表示该状态为必胜态。

• 对于没有任何后继移动的状态（游戏结束），\(\text{SG}(u) = 0 = \text{mex}(\emptyset) = 0\)，对应必败态。
• 若 \(\text{SG}(u)=0\)，根据 \(\text{mex}\) 的定义，这意味着 \(u\) 的所有后继状态 \(v_i\) 的 SG 值都不为 0（即 \(\text{SG}(v_i) \gt 0\)），这符合“必败态的任何移动都会进入必胜态”的性质。
• 若 \(\text{SG} \gt 0\)，根据 \(\text{mex}\) 的定义，这意味着 \(u\) 的后继状态中至少存在一个状态 \(v_j\) 满足 \(\text{SG}(v_j) = 0\)，这符合“必胜态至少有一种移动可以进入必败态”的性质。

Sprague-Grundy 定理

SG 定理是博弈论中最核心的定理，它指出任何一个 ICG 都可以等价于一个 Nim 游戏中的一堆石子，其石子数为该状态的 SG 值。

对于由 \(n\) 个独立的子游戏组成的复合游戏 \(G\)，其总状态的 SG 值为各子游戏状态 SG 值的异或和：\(\text{SG}(G) = \text{SG}(G_1) \oplus \text{SG}(G_2) \oplus \cdots \oplus \text{SG}(G_n)\)。

要证明复合游戏 \(G\) 的 SG 值（设为 \(x\)）确实等于各子游戏 SG 值的异或和。根据 SG 函数的定义，需要证明：

1. 对于任何 \(x' \lt x\)，都存在一个后继状态 \(G'\) 使得 \(\text{SG}(G') = x'\)
2. 对于任何后继状态 \(G'\)，都有 \(\text{SG}(G') \ne x\)

设 \(x = \text{SG}(G_1) \oplus \text{SG}(G_2) \oplus \cdots \oplus \text{SG}(G_n)\)。

证明 1（可达性）：设 \(k = x \oplus x'\)，由于 \(x' \lt x\)，在 \(x \oplus x'\) 的二进制表示中，最高位的 1（设在第 \(p\) 位）在 \(x\) 中必然是 1，而在 \(x'\) 中必然是 0。既然 \(x\) 的第 \(p\) 位是 1，根据异或性质，必然存在至少一个子游戏 \(G_i\)，其中 \(\text{SG}(G_i)\) 的第 \(p\) 位是 1，那么 \(\text{SG}(G_i) \oplus k \lt \text{SG}(G_i)\)。根据 SG 函数的定义，子游戏 \(G_i\) 一定存在一个后继状态 \(G_i'\) 使得 \(\text{SG}(G_i') = \text{SG}(G_i) \oplus k\)（因为 \(\text{SG}(G_i)\) 是其后继 SG 值的 \(\text{mex}\)，所以小于它的值一定能达到）。此时整个复合游戏的异或和变为 \(\text{SG}(G') = x \oplus \text{SG}(G_i) \oplus \text{SG}(G_i') = x \oplus k = x \oplus (x \oplus x') = x'\)，这证明了可以到达任何小于 \(x\) 的 SG 值。

证明 2（不可达性）：后继状态 \(G'\) 是通过移动其中一个子游戏 \(G_i\) 到 \(G_i'\) 得到的，若 \(\text{SG}(G') = x\)，即 \(\text{SG}(G_1) \oplus \dots \oplus \text{SG}(G_i') \oplus \dots \oplus \text{SG}(G_n) = \text{SG}(G_1) \oplus \dots \oplus \text{SG}(G_i) \oplus \dots \oplus \text{SG}(G_n)\)。等式两边同时异或掉相同的项，得到 \(\text{SG}(G_i') = \text{SG}(G_i)\)。这与 \(\text{SG}(G_i)\) 是其后继状态 SG 值的 \(\text{mex}\) 这一基础定义矛盾，因此 \(\text{SG}(G') \neq x\) 成立。

综上所述，\(\text{SG}(G)\) 完美符合 \(\text{mex}\) 的定义，定理得证。

例题：P10501 Cutting Game

给定一个 \(W \times H \ (2 \le W,H \le 200)\) 的矩形纸张，两名玩家轮流对纸张进行横向或纵向切割，每次切割将一片矩形纸张分成两片新的矩形。如果一名玩家切出了一个 \(1 \times 1\) 的格子，该玩家获胜。问在双方都采取最优决策略的情况下，先手是否必胜。

本题的关键在于获胜条件：切出 \(1 \times 1\) 格子的玩家获胜。观察发现，如果一个玩家在某一步切出了一个维度为 1 的矩形（例如 \(1 \times k\) 或 \(k \times 1\)），那么下一个玩家可以立即从该矩形中切出一个 \(1 \times 1\) 的格子从而直接获胜。因此，在最优策略下，任何玩家都不会主动切出维度为 1 的矩形，除非当前矩形无法再进行“安全”的切割（即切出的两个部分边长都 \(\ge 2\)）。此时，游戏等价于在一个“安全移动”集合上的博弈，当一名玩家无法再将矩形切成两个边长均 \(\ge 2\) 的小矩形时，他将不得不切出一个维度为 1 的矩形，从而输掉游戏。

该游戏是一个典型的公平组合游戏，可以使用 SG 定理求解。定义状态 \(\text{SG}(w,h)\) 表示宽度为 \(w\)、高度为 \(h\) 的矩形的博弈状态值。切割一个矩形会将原游戏分解为两个独立的子游戏，根据 SG 定理，一个移动的后继状态的 SG 值为两个子状态 SG 值的异或和。

\[\text{SG}(w, h) = \text{mex}(\{\text{SG}(k, h) \oplus \text{SG}(w-k, h) \mid 2 \le k \le w-2\} \cup \{\text{SG}(w, k) \oplus \text{SG}(w, h-k) \mid 2 \le k \le h-2\}) \]

对于 \(w \lt 4\) 且 \(h \lt 4\) 的矩形，如果它们无法被切割成两个边长均 \(\ge 2\) 的矩形，则其 \(SG\) 值为 0。

由于 \(W,H \le 200\)，可以预处理出所有可能的 \(\text{SG}(w,h)\) 值。对于每个状态，遍历所有可能的垂直切割位置和水平切割位置，记录出现的异或和，取最小未出现的非负整数。预处理完成后，对于每个测试用例，直接查询 \(\text{SG}(W,H)\)，若其值大于 0，则先手必胜，否则先手必败。

时间复杂度为 \(O(W \times H \times (W+H))\)。

#include <cstdio>
int sg[205][205];
bool vis[512]; // 标记后继状态的 SG 异或和
// 预计算 200*200 范围内所有矩形的 SG 值
void init() {
    for (int i = 2; i <= 200; i++) {
        for (int j = 2; j <= 200; j++) {
            for (int k = 0; k < 512; k++) vis[k] = false;
            // 垂直切割：将宽度 i 切成 k 和 i-k，保证两个新矩形的宽度都 >= 2
            for (int k = 2; k <= i - k; k++) {
                vis[sg[k][j] ^ sg[i - k][j]] = true;
            }
            // 水平切割：将高度 j 切成 k 和 j-k，保证两个新矩形的高度都 >= 2
            for (int k = 2; k <= j - k; k++) {
                vis[sg[i][k] ^ sg[i][j - k]] = true;
            }
            // 计算 mex (最小未出现的非负整数)
            int k = 0;
            while (vis[k]) k++;
            sg[i][j] = k;
        }
    }
}
int main()
{
    init(); // 预处理 SG 表
    int w, h;
    while (scanf("%d%d", &w, &h) == 2) {
        // SG 值大于 0 表示先手必胜，否则必败
        if (sg[w][h] > 0) printf("WIN\n");
        else printf("LOSE\n");
    }
    return 0;
}

习题：P10506 魔法珠

有 \(n \ (1 \le n \le 100)\) 堆魔法珠，每一堆的数量分别为 \(a_i \ (1 \le a_i \le 1000)\)，两人轮流进行操作：选择一堆数量 \(p \gt 1\) 的魔法珠；找到 \(p\) 的所有小于 \(p\) 的约数 \(b_1, b_2 \dots, b_m\)；将该堆珠子替换为这 \(m\) 堆，每堆数量分别为 \(b_1, \dots, b_m\)；从这 \(m\) 堆中选择一堆并将其移除。
游戏结束的条件是所有堆的数量都为 1（无法再进行操作），采用最佳策略，求先手还是后手获胜。

#include <cstdio>
int d[1005], sg[1005];
bool vis[1025];
// 预处理 1 到 1000 的 SG 值
void init() {
    for (int i = 2; i <= 1000; i++) {
        int cnt = 0, tot = 0;
        // 寻找 i 的所有真约数
        for (int j = 1; j < i; j++) {
            if (i % j == 0) {
                d[cnt] = j;
                cnt++;
                tot ^= sg[j];
            }
        }
        // 计算所有可能的后继状态的 SG 值
        for (int j = 0; j < 1025; j++) vis[j] = false;
        for (int j = 0; j < cnt; j++) vis[tot ^ sg[d[j]]] = true;
        // 求 mex
        int r = 0;
        while (vis[r]) r++;
        sg[i] = r;
    }
}
int main()
{
    init();
    int n; 
    while (scanf("%d", &n) == 1) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            int a; scanf("%d", &a);
            sum ^= sg[a];
        }
        // 若异或和不为 0，先手 Freda 必胜
        if (sum > 0) printf("freda\n");
        else printf("rainbow\n");
    }
    return 0;
}