第 50 章 博弈论¶
配套例题：BISHI34 甜蜜的博弈、BISHI35 【模板】巴什博弈、BISHI36 【模板】扩展巴什博弈 来源：S3 day5 贪心课件里的博弈部分
竞赛里的博弈论几乎只考一类：公平组合游戏（Impartial Game）。它的定义是：
- 两人轮流行动，双方可选的行动集合完全相同（与执棋方无关）；
- 信息完全公开，无随机成分；
- 无法行动者判负（normal play convention）；
- 游戏必然在有限步内结束。
这类游戏的全部理论可以浓缩成下面两条递归定义。
50.1 必胜态与必败态¶
给每个局面染色：
- 必败态（P-position）：所有后继都是必胜态。（先手必输）
- 必胜态（N-position）：存在某个后继是必败态。（先手必赢）
边界：无法行动的局面是必败态。
注意这两句的量词——「所有」对必败，「存在」对必胜，写反就全反了。
直觉：必胜态就是「我能把烂摊子甩给对手」，必败态就是「我怎么走都是把好局面送给对手」。
打表：解决一切博弈题的第一步¶
任何博弈题都可以先打一张小表，这是最重要的实战技能：
def solve_small(n, moves):
"""moves(k) 返回从局面 k 出发能到达的所有局面（必须都 < k）。
返回 win[0..n]，win[k] 为 True 表示局面 k 先手必胜。"""
win = [False] * (n + 1) # 初值 False 同时也是边界：无路可走的局面必败
# 按 k 递增计算，保证用到 win[nxt] 时它已经算好（后继局面严格更小）
for k in range(n + 1):
# 「存在一个后继是必败态」-> 当前必胜；后继为空时 any 返回 False，正好是必败
win[k] = any(not win[nxt] for nxt in moves(k))
return win
打出 30–50 项，然后找周期或找规律。绝大多数笔试博弈题的答案都是
打表是手段，不是答案。 找到规律后必须回去证明（说清「为什么这些是必败态」）， 否则很容易被边界上的零星例外坑掉——BISHI34 就有三个「小奇点」。
50.2 巴什博弈（Bash Game）¶
\(n\) 个石子，每次取 \(1..m\) 个，取到最后一个者胜。
结论：先手必败 \(\iff (m+1) \mid n\)。
证明：把石子按 \(m+1\) 一组切分。
- 若 \((m+1) \mid n\)：无论先手取 \(x \in [1, m]\)，后手都能取 \(m+1-x\) 把这一组补满， 局面永远回到「剩余是 \(m+1\) 的倍数」，最终后手拿走最后一颗。
- 否则：先手第一步取 \(n \bmod (m+1)\) 颗，把上述必败态丢给对手。
\(m \ge n\) 的情形自动覆盖：此时 \(n \bmod (m+1) = n \ne 0\)，先手一次拿光必胜。
50.3 扩展巴什博弈¶
每次取 \(x \in [l, r]\) 个；剩余石子少于 \(l\) 时无法行动，取到最后一个者胜。
结论：先手必胜 \(\iff n \bmod (l+r) \ge l\)。
推导：剩余石子 \(s \in [0, l-1]\) 时当前行动者无法取子，直接判负—— 这 \(l\) 个数构成「必败区」。以 \(l+r\) 为周期考察：
- 若 \(s \bmod (l+r) \in [l, r]\)：先手可以取 \(s \bmod (l+r)\) 颗 （取子量在 \([l, r]\) 内，合法），把剩余变成 \(l+r\) 的倍数，落回必败区的起点；
- 若 \(s \bmod (l+r) \in [0, l-1]\)：先手取 \(x \in [l, r]\) 后， \((s-x) \bmod (l+r)\) 落进 \([l, r]\)，也就是把必胜态还给对手。 这样一路下去，先手最终面对 \([0, l-1]\) 而输。
特例自然覆盖：\(n < l\) 时 \(n \bmod (l+r) = n < l\)，先手无法行动即负。
判定的模数是 \(l+r\) 而不是 \(r+1\)。普通巴什博弈是 \(l = 1\) 的特例： \(n \bmod (1+r) \ge 1 \iff (r+1) \nmid n\)，与 50.2 一致。
50.4 尼姆博弈（Nim）与 SG 函数¶
尼姆博弈¶
\(k\) 堆石子，每次从任意一堆取任意多个（至少 1 个），取到最后一个者胜。
结论（Bouton 定理）：先手必败 \(\iff a_1 \oplus a_2 \oplus \cdots \oplus a_k = 0\)。
这个异或和称为 Nim 和。
from functools import reduce
from operator import xor
lose = reduce(xor, piles, 0) == 0 # Nim 和为 0 即必败；初值 0 是异或的幺元
证明要点：
- Nim 和为 0 时，任何一步都会使它变成非 0（改动一堆必然改变异或和）；
- Nim 和非 0 时，设最高位为第 \(b\) 位，取一堆在第 \(b\) 位为 1 的石子， 可以把它改成 \(a_i \oplus (\text{Nim 和})\)（这个值一定小于 \(a_i\)），使异或和归零；
- 终局（全空）的 Nim 和是 0，是必败态。
SG 函数¶
对更一般的公平组合游戏，用 SG 值（Sprague–Grundy）：
其中 \(\operatorname{mex}(S)\) 是不属于 \(S\) 的最小非负整数（minimum excludant）。
| 性质 | 内容 |
|---|---|
| 必败判定 | \(\operatorname{SG}(x) = 0 \iff x\) 是必败态 |
| Sprague–Grundy 定理 | 多个独立游戏的和，SG 值 = 各子游戏 SG 值的异或 |
尼姆博弈就是它的特例：一堆 \(a\) 个石子的 SG 值恰好是 \(a\)，所以整体 SG = 异或和。
def sg_table(n, moves):
"""打 SG 表。moves(k) 返回 k 的所有后继局面（必须 < k）。"""
sg = [0] * (n + 1) # sg[0] = 0：无路可走的局面 SG 值为 0，即必败
for k in range(1, n + 1): # 递增计算，用到的后继 SG 值都已就位
s = {sg[nxt] for nxt in moves(k)} # 所有后继的 SG 值集合
g = 0
while g in s: # 求 mex：从 0 开始找第一个不在集合里的非负整数
g += 1
sg[k] = g # 后继里没有 0（即无必败后继）时 g == 0，本局面必败
return sg
什么时候需要 SG 而不是简单的胜负表？ 只有当游戏能拆成若干独立子游戏（比如「多堆石子」「多条链」）时， SG 的异或才有意义。单一局面的游戏只需要 0/1 的胜负表—— 本章三道例题都属于后者，打胜负表就够了。
50.5 常见博弈模型速查¶
| 模型 | 规则 | 先手必败条件 |
|---|---|---|
| 巴什博弈 | 取 \(1..m\) 个 | \((m+1) \mid n\) |
| 扩展巴什 | 取 \(l..r\) 个 | \(n \bmod (l+r) < l\) |
| 尼姆博弈 | 多堆任取 | \(\bigoplus a_i = 0\) |
| 威佐夫博弈 | 两堆，取一堆任意多或两堆取同样多 | \(\lfloor \phi \cdot k \rfloor\) 型（黄金分割） |
| 阶梯尼姆 | 只能往前一级移 | 奇数级的异或和为 0 |
| 反常游戏（取到最后者负） | Misère | 结论与正常游戏不同，需单独讨论 |
注意胜负约定：本章默认「无法行动者负」。 若题目说「取到最后一个石子的人输」，那是 Misère 规则，结论可能完全不同， 必须重新打表。
50.6 例题¶
BISHI35 【模板】巴什博弈（中等）¶
\(T \le 2\times10^6\) 组，每组给 \(n, m \le 10^9\)，判断先手能否必胜。 题面见 BISHI35 原题（牛客）。
结论一行，这题真正的考点是 IO：输入有 \(4\times10^6\) 个 token，输出有 \(2\times10^6\) 行。
import sys
def main() -> None:
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
p = 1 # data[0] 是组数，每组吃掉 2 个 token
for _ in range(t):
n = int(data[p]); m = int(data[p + 1]); p += 2
# 余数非 0 -> 先手先取走余数，把「剩余是 m+1 的倍数」这个必败态丢给对手
# m >= n 时余数就是 n（非 0），公式自动给出必胜，不用特判
out.append("YES" if n % (m + 1) else "NO") # (m+1) | n 时先手必败
sys.stdout.write("\n".join(out) + "\n")
main()
- 是 \((m+1) \mid n\) 判负，不是 \(m \mid n\)。
- \(m \ge n\) 时不用特判：\(n \bmod (m+1) = n \ne 0\)，公式自动给出「必胜」 （样例第一组 \(n=3, m=5\) 即是）。
- 输出是大写
YES/NO（易错点：大小写）。 - \(T = 2\times10^6\) 时逐行
input()/print必然 TLE， 必须整块读入 + 一次性写出，见 20-输入输出处理。
题解见 solutions/BISHI35.py。
BISHI36 【模板】扩展巴什博弈（较难）¶
\(T \le 2\times10^6\) 组，每组给 \(n, l, r\)，每次取 \(x \in [l, r]\) 个，取到最后者胜。 题面见 BISHI36 原题（牛客）。
import sys
def main() -> None:
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
p = 1
for _ in range(t):
n = int(data[p]); l = int(data[p + 1]); r = int(data[p + 2]); p += 3
# 周期是 l+r：余数落在 [l, r] 内先手可一次清成整周期；落在 [0, l-1] 则动弹不得或必输
# n < l 时余数就是 n < l，公式已覆盖「无法行动即负」
out.append("YES" if n % (l + r) >= l else "NO")
sys.stdout.write("\n".join(out) + "\n")
main()
- 模数是 \(l+r\)，写成 \(r+1\) 就退化成普通巴什博弈了。
- \(n < l\) 一定是
NO，公式已覆盖（\(n \bmod (l+r) = n < l\)），别再画蛇添足。 - 样例第三组 \(n=7, l=2, r=5\)：\(7 \bmod 7 = 0 < 2\) →
NO，正好卡在整除边界上。 这组数据就是用来卡「忘了取模后可能为 0」的写法的。
题解见 solutions/BISHI36.py。
BISHI34 甜蜜的博弈（简单）¶
剩余 \(k\) 个钻石时，可以取 1 个；若 \(2 \mid k\) 可以取 2 个；若 \(5 \mid k\) 可以取 5 个。 无法取走钻石者输，Alice 先手。\(T \le 100\)，\(N \le 10^9\)。 题面见 BISHI34 原题（牛客）。
这题就是 50.1「打表找规律」的完整演练——注意可选操作依赖于 \(k\) 本身， 不是固定的取子集合，所以没有现成公式可套。
先打表（\(k=0\) 是必败态，因为无法行动）：
k : 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20
态: L W W L W W L W W L W L W L W L W L W L W
规律：必败态 \(= \{0, 3, 6\} \cup \{k \ge 9 \text{ 且 } k \text{ 为奇数}\}\)。
证明（\(k \ge 7\) 部分）：
- 偶数 \(k \ge 8\) 必胜：\(k = 8\) 时取 2 到达 6（必败）； \(k \ge 10\) 时取 1 到达奇数 \(k-1 \ge 9\)（必败）。
- 奇数 \(k \ge 9\) 必败：\(k\) 是奇数，\(2 \nmid k\)，所以只能取 1， 或者（当 \(5 \mid k\) 时）取 5。取 1 到达偶数 \(k-1 \ge 8\)（必胜）； 取 5 到达偶数 \(k-5\)（\(k=15\) 时到 10，\(k \ge 25\) 时到 \(\ge 20\)，都是必胜）。 所有后继都是必胜态，故本身必败。
\(0..8\) 的零散值按小表特判。
import sys
LOSE_SMALL = {0, 3, 6} # 9 以下的必败态，由本地小表逐项验出，不能靠公式推
def main() -> None:
data = sys.stdin.buffer.read().split()
t = int(data[0])
out = []
for i in range(1, t + 1): # 每组只有一个数，token 与组号一一对应
n = int(data[i])
# 必败态：0、3、6，或者 >= 9 的奇数。N 到 1e9，必须 O(1) 判定而不是打表
lose = n in LOSE_SMALL or (n >= 9 and n % 2 == 1)
out.append("Bob" if lose else "Alice") # 先手必败则后手 Bob 赢
sys.stdout.write("\n".join(out) + "\n")
main()
四个要点：
- 别漏掉 3 和 6 这两个「小奇点」。只写「奇数且 \(\ge 9\)」会在 \(N = 3\) 上 WA， 而样例第二组恰好就是 3——出题人知道你会漏。
- \(N \le 10^9\)，绝不能打 \(10^9\) 的表。打表只在纸上（或本地）做， 提交的代码必须是 \(O(1)\) 判定。
- 取 5 的条件是 \(5 \mid k\) 且 \(k \ge 5\)，取 2 同理。 \(k=5\) 时取 5 到 0 必胜，这正是 5 与 15/25 结论不同的原因。
- 输出的是名字而不是 YES/NO：必败输出
Bob，必胜输出Alice。 样例第三组 \(5201314\) 是偶数且不在 \(\{0,6\}\) 里 →Alice。
题解见 solutions/BISHI34.py。
本题的方法论值得单独记住： ① 定义必败态（无法行动者负）→ ② 本地打 30 项小表 → ③ 猜规律 → ④ 分奇偶 / 分区间证明 → ⑤ 写 \(O(1)\) 判定 → ⑥ 用小表回测所有 \(k \le 50\)。 第 6 步（回测）能抓住 90% 的「小奇点」遗漏。
50.7 本章速查¶
| 概念 | 定义 |
|---|---|
| 必败态 | 所有后继都是必胜态；无法行动的局面是必败态 |
| 必胜态 | 存在一个后继是必败态 |
| SG 值 | \(\operatorname{mex}\) of 后继的 SG 值 |
| SG = 0 | 等价于必败态 |
| Sprague–Grundy | 独立子游戏的和，SG = 各子游戏 SG 的异或 |
| 模型 | 先手必败条件 |
|---|---|
| 巴什（取 \(1..m\)） | \((m+1) \mid n\) |
| 扩展巴什（取 \(l..r\)） | \(n \bmod (l+r) < l\) |
| 尼姆（多堆任取） | \(\bigoplus a_i = 0\) |
| 解题流程 | 步骤 |
|---|---|
| 1 | 确认是公平组合游戏、确认胜负约定 |
| 2 | 本地打 30–50 项小表 |
| 3 | 找周期 / 模数 / 位运算规律 |
| 4 | 回去证明（分奇偶、分区间） |
| 5 | 写 \(O(1)\) 或 \(O(\log)\) 判定 |
| 6 | 用小表回测，抓「小奇点」 |
| 坑 | 说明 |
|---|---|
| 量词写反 | 必败是「所有」，必胜是「存在」 |
| Misère 规则 | 「取到最后者负」要重新打表 |
| 小奇点 | 规律往往在小数值处有例外（BISHI34 的 3 和 6） |
| 打大表 | \(N \le 10^9\) 时表只能打在纸上 |
| 输出格式 | YES/NO 还是 Alice/Bob，逐字核对 |
| \(T\) 到 \(10^6\) | IO 是真正的瓶颈，整块读 + 一次写 |