InoueMoby's Blog

前言

两个人轮流拿石子。桌上有一堆石子，每次可以拿 1 到 3 颗，拿走最后一颗的人赢。先手还是后手赢？

你也许能凭直觉判断：如果石子数是 4 的倍数，后手赢（先手拿 $x$ 颗，后手拿 $4-x$ 颗，总能凑够 4）；否则先手赢（拿掉余数，之后变成后手）。

但如果有多堆石子，每堆可以拿任意颗呢？直觉不够用了。1910 年，哈佛数学家 Charles Bouton 证明了一个优美的结论：把每堆石子数异或起来，结果是 0 则后手赢，非 0 则先手赢。 这就是 Nim 游戏。

问题的本质

先手必胜和先手必败

博弈论中的核心概念：

必胜态（N 态）：当前玩家有策略使得无论对手怎么走，自己最终获胜。
必败态（P 态）：无论当前玩家怎么走，对手都有获胜的策略。

判断规则（从终局倒推）：

终局（没有合法操作）是 P 态。
如果一个状态的所有后继都是 N 态，则它是 P 态（你不管怎么走都给对手一个必胜态）。
如果一个状态有一个后继是 P 态，则它是 N 态（你可以走一步让对手面对必败态）。

单堆 Nim

一堆 $n$ 颗石子，每次拿 1 到 $k$ 颗。终局 $n=0$ 是 P 态。倒推：

$n$	0	1	2	3	4	5	6	7	8
状态	P	N	N	N	P	N	N	N	P

规律： $n \bmod (k+1) = 0$ 时 P 态，否则 N 态。 $k=3$ 时就是 4 的倍数。

多堆 Nim

$n$ 堆石子，第 $i$ 堆有 $a_i$ 颗。每次从一堆中拿任意正数颗。Bouton 定理：

\text{先手必胜} \iff a_1 \oplus a_2 \oplus \cdots \oplus a_n \neq 0

其中 $\oplus$ 是异或（XOR）。

为什么？ 两个关键性质：

如果 XOR 和 $\neq 0$ ，一定存在一种拿法使得拿完后 XOR 和 $= 0$ 。（找到最高位 1 所在的堆，拿掉足够的石子。）
如果 XOR 和 $= 0$ ，无论怎么拿，拿完后 XOR 和一定 $\neq 0$ 。（因为你改变了某一堆的值，XOR 和一定跟着变。）

所以 XOR 和 $= 0$ 的状态只能转移到 XOR 和 $\neq 0$ 的状态，反过来则可以。终局（全是 0）的 XOR 和 $= 0$ ，所以 XOR 和 $= 0$ 就是 P 态。

理论 + 代码

Nim 游戏判定

#include <cstdio>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);
    int xor_sum = 0;
    for (int i = 0; i < N; i++) {
        int A;
        scanf("%d", &A);
        xor_sum ^= A;    // ① 异或累积
    }
    // ② XOR 和为 0 → 后手赢，否则先手赢
    if (xor_sum == 0)
        printf("Second\n");   // 后手必胜
    else
        printf("First\n");    // 先手必胜
}

① xor_sum ^= A：异或满足交换律和结合律，从左到右异或就行。
② XOR 和 $= 0$ 意味着先手无法做出让 XOR 和保持 0 的操作，而后手总能恢复 XOR 和为 0。

走一遍过程：3 堆，分别是 3, 4, 5。

$3 \oplus 4 \oplus 5 = 011 \oplus 100 \oplus 101 = 010 = 2 \neq 0$ 。先手必胜。

先手应该怎么走？最高位是第 1 位（从右数第 2 位），对应的堆是 $3 = 011$ 。把 $3$ 变成 $3 \oplus 2 = 1$ ，即从第一堆拿 2 颗。拿完后是 $1, 4, 5$ ， $1 \oplus 4 \oplus 5 = 001 \oplus 100 \oplus 101 = 000 = 0$ 。✓

Sprague-Grundy 定理

很多博弈游戏不是 Nim 但可以等价为 Nim。SG 定理说：每个游戏状态可以映射到一个非负整数 $g$ （SG 值），然后整个游戏等价于 Nim 游戏，其中每堆石子数就是各子游戏的 SG 值。

g(s) = \operatorname{mex}\{g(s') : s' \text{ 是 } s \text{ 的后继}\}

$\operatorname{mex}(S)$ = 不在集合 $S$ 中的最小非负整数。

集合 $S$	mex
{}	0
{0}	1
{0,1}	2
{0,2}	1
{1,2}	0

终局的 SG 值 = 0（没有后继，mex(空集) = 0）。和 Nim 的 P 态对应。

SG 函数的代码实现：

// 计算单个状态的 SG 值
// succs 是当前状态的所有后继状态的 SG 值
int sg_value(const vector<int>& succs) {
    set<int> s(succs.begin(), succs.end());
    int g = 0;
    while (s.count(g)) g++;  // ① mex：找最小的不在集合中的非负整数
    return g;
}

// 更常见的模式：预处理所有状态的 SG 值
// 比如每次可以从一堆石子中拿 1, 2, 或 3 颗
int sg[100010];
void calc_sg(int n, vector<int> moves) {
    sg[0] = 0;  // ② 终局 SG = 0
    for (int i = 1; i <= n; i++) {
        set<int> reachable;
        for (int m : moves) {
            if (i >= m) reachable.insert(sg[i - m]);  // ③ 收集所有后继的 SG
        }
        int g = 0;
        while (reachable.count(g)) g++;
        sg[i] = g;  // ④ mex
    }
}

① mex 的实现很直觉：从 0 开始，只要在集合里就 +1，直到找到不在集合里的数。
② 终局（石子数为 0）的 SG 值为 0，这是 mex 的定义保证的。
③ 对每个合法操作，算出后继状态的 SG 值。
④ 最终的 SG 值就是这些后继 SG 值的 mex。

多个独立子游戏怎么组合？ 和 Nim 完全一样——把各子游戏的 SG 值异或起来。XOR 为 0 则后手赢，否则先手赢。这就是 SG 定理的核心。

例题

例题 1：M&A 060 — Stones Game 1（★2）

题目： $N$ 个石子，两人轮流取，每次取 1 到 3 个。不能取的人输。双方最优策略下，谁赢？

数据范围： $1 \le N \le 10^{12}$

—— AtCoder M&A 060

思路：经典 Nim 取石子（每次 1~3）。从小规模推规律：

$N$	1	2	3	4	5	6	7	8
赢家	先	先	先	后	先	先	先	后

规律： $N \bmod 4 = 0$ 时后手赢，否则先手赢。因为先手可以取 $N \bmod 4$ 个，使得剩下 $4k$ 个；之后无论后手取几个（1~3），先手都取 $(4 - \text{后手取的个数})$ ，保持剩余石子是 4 的倍数。

代码：

#include <cstdio>
using namespace std;

int main() {
    long long N;
    scanf("%lld", &N);
    printf("%s\n", N % 4 != 0 ? "First" : "Second");
}

例题 2：M&A 061 — Stones Game 2（★2）

题目： $N$ 个石子，当前有 $a$ 个时可以取 1 到 $\lfloor a/2 \rfloor$ 个。不能取的人输。双方最优策略下，谁赢？

数据范围： $1 \le N \le 10^{18}$

—— AtCoder M&A 061

思路： $N \le 10^{18}$ 太大，不能用 DP。需要找规律。先手算小规模：

$N$	1	2	3	4	5	6	7	8	9	10
赢家	后	先	后	先	后	先	先	后	先	后

看起来规律不那么简单。但实际上，这道题有一个巧妙的结论：如果 $N$ 在二进制表示中 1 的个数是偶数，则后手赢；奇数则先手赢（这需要证明，但代码很简单）。

不过这里给出 DP 做法处理 $N \le 10^5$ 的部分分：

#include <cstdio>
using namespace std;

// 只处理 N <= 10^5
bool win[100010];

int main() {
    long long N;
    scanf("%lld", &N);

    if (N > 100000) {
        // 大数情况下需要找规律
        // 经过观察：先手必胜当且仅当 ... （见正文理论）
        // 简单起见，这里只给出部分分代码
        return 0;
    }

    win[0] = false;  // 0 个石子，当前玩家输
    for (int i = 1; i <= N; i++) {
        win[i] = false;
        for (int k = 1; k <= i / 2; k++) {  // ① 枚举所有合法操作
            if (!win[i - k]) {               // ② 如果存在一个操作让对手处于必败态
                win[i] = true;
                break;
            }
        }
    }
    printf("%s\n", win[N] ? "First" : "Second");
}

逐行解析：

② 博弈论 DP 的核心：如果一个状态的所有后继状态都是必胜态，则当前是必败态；如果存在一个后继是必败态，则当前是必胜态。

例题 3：Tessoku Book — A32 Game 1

题目： $N$ 个石子，每次可以取 $A$ 个或 $B$ 个。不能取的人输。双方最优策略下，谁赢？

数据范围： $2 \le N \le 100000$ ， $1 \le A < B \le N$

—— AtCoder Tessoku Book A32

思路：和例题 1 类似，但可以取的数量固定为 $A$ 或 $B$ 。用 DP： $win[i] = !(win[i-A] \land win[i-B])$ （前提是 $i \ge A$ 或 $i \ge B$ ）。

代码：

#include <cstdio>
using namespace std;

bool win[100010];

int main() {
    int N, A, B;
    scanf("%d%d%d", &N, &A, &B);

    win[0] = false;
    for (int i = 1; i <= N; i++) {
        win[i] = false;
        if (i >= A && !win[i - A]) win[i] = true;  // ① 取 A 个后对手必败
        if (i >= B && !win[i - B]) win[i] = true;  // ② 取 B 个后对手必败
    }
    printf("%s\n", win[N] ? "First" : "Second");
}

逐行解析：

①② 只有两个选择（取 $A$ 或取 $B$ ）。只要有一个选择能让对手进入必败态，当前就是必胜态。

例题 4：Tessoku Book — A34 Game 3

题目： $N$ 堆石子，第 $i$ 堆有 $A_i$ 个。每次选一堆，取 $X$ 个或 $Y$ 个。所有堆的石子数都 $< X$ 时不能操作，输。谁赢？

数据范围： $1 \le N \le 100000$ ， $1 \le X < Y \le 100000$

—— AtCoder Tessoku Book A34

思路：Nim 博弈 + SG 函数。每堆石子独立，先算一堆的 SG 值（博弈等价于”取 $X$ 或 $Y$ 个，取不了输”），然后所有堆的 SG 值异或起来。如果异或结果 $\ne 0$ ，先手赢。

单堆的 SG 值： $sg[n] = \text{mex}(sg[n-X], sg[n-Y])$ （当 $n \ge X$ 时）。 $n < X$ 时 $sg[n] = 0$ 。

但实际上这道题有个更简单的结论：对每堆 $A_i$ ，计算 $sg\_value = (A_i \bmod (X+Y))$ 的 SG 值，然后异或。

由于 $N = 10^5, A_i \le 10^5$ ，可以预处理所有 SG 值：

代码：

#include <cstdio>
using namespace std;

int sg[100010];

int main() {
    int N, X, Y;
    scanf("%d%d%d", &N, &X, &Y);

    // ① 预处理 SG 值
    for (int i = 0; i <= 100000; i++) {
        bool seen[200] = {};
        if (i >= X) seen[sg[i - X]] = true;
        if (i >= Y) seen[sg[i - Y]] = true;
        for (int v = 0; ; v++) {
            if (!seen[v]) { sg[i] = v; break; }  // ② mex
        }
    }

    int xor_sum = 0;
    for (int i = 0; i < N; i++) {
        int a;
        scanf("%d", &a);
        xor_sum ^= sg[a];  // ③ 异或所有堆的 SG 值
    }
    printf("%s\n", xor_sum != 0 ? "First" : "Second");
}

逐行解析：

② mex（minimum excluded value）：集合中没出现过的最小非负整数。
③ Nim 定理：多个独立博弈的组合，先手必胜 $\Leftrightarrow$ 所有博弈的 SG 值异或 $\ne 0$ 。

例题 5：TB A33 — Game 2（Nim 博弈）

题目： $N$ 堆石子，第 $i$ 堆有 $A_i$ 个。两名玩家交替操作：每次选一堆，取走至少 1 个石子。取不了的人输。双方最优策略下，先手赢还是后手赢？

数据范围： $2 \le N \le 10^5$ ， $1 \le A_i \le 10^9$

—— AtCoder Tessoku Book A33

思路：经典的 Nim 博弈。结论：如果所有堆的石子数异或和为 0，后手必胜；否则先手必胜。

为什么？直觉理解：如果异或和 $X \ne 0$ ，先手总能找到一堆石子，从中取走一些使异或和变为 0。而如果异或和已经是 0，无论怎么取，异或和都会变成非 0。最终状态（所有堆为 0）的异或和是 0，所以异或和 0 = 后手必胜。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N;
    scanf("%d", &N);

    int xor_sum = 0;  // ① 异或和
    for (int i = 0; i < N; i++) {
        int A;
        scanf("%d", &A);
        xor_sum ^= A;   // ② 累计异或
    }

    if (xor_sum == 0)    // ③ 异或和为 0 → 后手赢
        printf("Second\n");
    else                  // ④ 异或和非 0 → 先手赢
        printf("First\n");
}

逐行解析：

② 用异或累计所有堆的石子数。异或的性质：相同为 0，不同为 1。
③④ Nim 博弈的核心定理： $A_1 \oplus A_2 \oplus \cdots \oplus A_N = 0$ 时后手必胜，否则先手必胜。
验证： $N=2, A=[7,7]$ ， $7 \oplus 7 = 0$ → Second。✓ 验证： $N=2, A=[5,8]$ ， $5 \oplus 8 = 13 \ne 0$ → First。✓

参考文献

教材讲解 — 競技プログラミングの鉄則第 5 章

5.7 B32 Game 5（博弈论 DP 解说，勝ち/負け状態判定）

配套教材

「アルゴリズムと数学」書籍 3.8 節「ゲーム問題」

基础练习 — アルゴリズムと数学演習問題集

系统练习 — 競技プログラミングの鉄則

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

博弈论基础

拿石子游戏的必胜策略——Nim游戏与Sprague-Grundy定理

前言

问题的本质

先手必胜和先手必败

单堆 Nim

多堆 Nim

理论 + 代码

Nim 游戏判定

Sprague-Grundy 定理

例题

例题 1：M&A 060 — Stones Game 1（★2）

例题 2：M&A 061 — Stones Game 2（★2）

例题 3：Tessoku Book — A32 Game 1

例题 4：Tessoku Book — A34 Game 3

例题 5：TB A33 — Game 2（Nim 博弈）

参考文献

系列索引

博弈论基础