企业官网建设流程全解析

1. 从“背结论”到“推结论”：博弈论在竞赛中的真实定位

很多人第一次接触博弈论，是在竞赛题库里刷到一堆“取石子”“拿硬币”“切巧克力”的题。当时我的做法很粗暴：把几种经典模型（巴什博弈、威佐夫博弈、尼姆博弈）的必胜条件背下来，看到类似的题就往公式上套。短期确实能过题，但一旦题目稍微变形——比如石子堆数变了、取子规则加了限制、胜负判定改成“取到最后一个输”——立刻就懵了。

后来我才意识到，博弈论题目的核心不是记忆，而是状态与胜负关系的推导。所有公平组合游戏（Impartial Combinatorial Game）的底层逻辑，都可以归结为一句话：当前局面是必胜态还是必败态，取决于它能否转移到某个必败态。这个定义看起来简单，但它能推出后面所有模型，包括那些看起来毫无规律的取子游戏。

这篇文章我打算把博弈论从零到能打区域赛的完整知识链路梳理一遍。不是那种“结论+代码”的速查表，而是把每个结论背后的推导过程、为什么这样定义、怎么从定义一步步算出公式，全部摊开讲清楚。适合两类人：一是刚学博弈论、被各种公式绕晕的选手；二是打过一些题但遇到变形就不会做的选手。如果你属于后者，大概率是因为跳过了推导直接背结论。

全文会覆盖：必胜态/必败态的严格定义与证明方法、巴什博弈的完整推导、威佐夫博弈的贝蒂定理证明思路、尼姆博弈与SG定理的来龙去脉、反尼姆博弈的坑点、以及SG函数在非取子类游戏（如分割游戏、图上游戏）中的应用。每个模型我都会给出“为什么是这样”的分析，而不是只丢一个公式。

2. 必胜态与必败态：整个博弈论体系的公理基础

2.1 两个定义，撑起所有公平组合游戏

在公平组合游戏中，两个玩家轮流操作，操作规则完全对称（即不存在某个操作只有一方能做），无法操作的一方判负。这是最常见的约定，后面讨论的模型默认都基于这个前提。

在这个框架下，我们定义：

• 必败态（P-position，Previous player wins）：当前玩家无论怎么操作，都会把局面交给对手一个必胜态。换句话说，当前玩家在这个局面下没有获胜策略。
• 必胜态（N-position，Next player wins）：当前玩家存在至少一种操作，能把局面交给对手一个必败态。

这两个定义是递归的。终止局面（无法操作的局面）是必败态，因为轮到谁谁就输了。然后所有能一步到达终止局面的状态是必胜态，所有只能到达必胜态的状态是必败态，以此类推。

注意：这里的“必胜/必败”是针对“当前轮到操作的玩家”而言的。同一个局面，如果换一个玩家来描述，胜负属性不变，因为规则对称。

2.2 为什么这个定义能推出所有结论

很多人会问：凭什么说“能到达必败态就是必胜态”？这不是循环定义吗？

其实不是。这是一个有向无环图上的递归定义。游戏的状态转移构成一个有向无环图（因为游戏必须在有限步内结束，不能无限循环），终止节点是出度为0的节点。我们在这个DAG上做如下标记：

1. 所有出度为0的节点标记为P。
2. 如果一个节点的所有后继都是N，则标记为P。
3. 如果一个节点存在至少一个后继是P，则标记为N。

这个标记过程是良定义的，因为DAG可以拓扑排序，从终止节点倒推。标记完成后，N节点就是必胜态，P节点就是必败态。证明很简单：如果当前是N，当前玩家走到那个P后继，对手面对P，根据定义对手必败；如果当前是P，当前玩家无论走到哪个后继，那个后继都是N，对手面对N，对手有必胜策略。

所以整个博弈论的核心任务就变成了：给定一个游戏的状态转移规则，判断初始状态是N还是P。对于状态空间小的问题，直接DP递推即可；对于状态空间大的问题，需要找规律或数学公式。

2.3 从定义出发的三种解题路径

在实际竞赛中，判断N/P有三条路：

• 暴力DP打表：状态数在可接受范围内（比如10^6以内），直接按拓扑序递推。这是最稳的方法，也是找规律的前提。
• 找规律/数学公式：打表后观察N/P的分布规律，猜测公式，再用数学归纳法证明。巴什博弈、威佐夫博弈都是这条路。
• SG定理分解：对于多个独立子游戏组合的局面，用SG函数把每个子游戏映射成一个数，再用异或判断。尼姆博弈及其变种走这条路。

三条路不是互斥的。很多时候先用DP打表，再找规律，最后用SG定理统一解释。下面逐个展开。

3. 巴什博弈：从打表到公式的完整推导链

3.1 问题描述与朴素DP

巴什博弈（Bash Game）是最简单的取子游戏：有一堆n个石子，两人轮流取，每次至少取1个，至多取m个，取到最后一个石子的人获胜。

按照第2节的定义，我们可以直接写DP：

• 状态：剩余石子数i。
• 终止：i=0是必败态（轮到谁谁输，因为没石子可取）。
• 转移：从i可以走到i-1, i-2, ..., i-m（前提是i-k >= 0）。
• 判断：如果存在k使得i-k是必败态，则i是必胜态；否则i是必败态。

用代码写出来就是：

def bash_dp(n, m): # dp[i] = True 表示剩余i个石子时当前玩家必胜 dp = [False] * (n + 1) for i in range(1, n + 1): for k in range(1, min(i, m) + 1): if not dp[i - k]: dp[i] = True break return dp

跑一下n=15, m=3的结果：

规律非常明显：i是(m+1)的倍数时是必败态，否则是必胜态。

3.2 为什么是(m+1)的倍数：构造性证明

打表看出规律后，需要证明。证明分两步：

第一步：证明(m+1)的倍数是必败态。

假设当前剩余石子是k(m+1)。无论当前玩家取x个（1 <= x <= m），对手都可以取(m+1-x)个，使得这一轮总共取了(m+1)个，剩余石子变成(k-1)(m+1)。对手总能这样做，直到剩余0个，此时当前玩家面对0个，必败。

这里的关键是：对手的回应策略是“补足m+1”。因为x在1到m之间，所以m+1-x也在1到m之间，是对手的合法操作。这个策略能一直执行下去，所以k(m+1)是必败态。

第二步：证明非(m+1)倍数的是必胜态。

假设当前剩余石子是k(m+1)+r，其中1 <= r <= m。当前玩家取r个，剩余k(m+1)个，交给对手一个必败态。所以当前玩家必胜。

两步合起来，结论成立。这个证明是构造性的，不仅证明了结论，还给出了必胜策略：每次取的石子数 = 当前石子数 mod (m+1)，如果余数不为0；如果余数为0，则无论怎么取都会输。

3.3 变形与坑点：取到最后一个输

巴什博弈最常见的变形是“取到最后一个石子的人输”（Misère版本）。这时候结论会变。

打表看看n=15, m=3, 取到最后一个输的情况：

注意i=0变成了必胜态（因为轮到谁谁“赢”，规则反了）。规律变成：i mod (m+1) == 1时是必败态，其余是必胜态（除了i=0特殊）。

为什么？因为当剩余1个时，当前玩家必须取1个，取完对手面对0个，按照“取到最后一个输”的规则，对手输了，所以当前玩家赢了？等等，这里要仔细。

“取到最后一个输”的意思是：谁取走最后一个石子谁输。所以如果剩余1个，当前玩家取走它，当前玩家就输了。所以剩余1个是必败态。剩余0个呢？游戏已经结束，上一手取走最后一个的人输了，所以面对0个的玩家是赢了。所以0是必胜态。

从1开始推：1是P，2可以走到1（取1个），所以2是N；3可以走到1（取2个）或2，所以3是N；4可以走到1（取3个），所以4是N；5只能走到2,3,4（取1,2,3个），全是N，所以5是P。规律确实是i mod (m+1) == 1时P。

实操心得：Misère版本的巴什博弈在竞赛中出现的频率不低，但很多人只背了标准版的公式，遇到Misère就翻车。记住一个原则：Misère版本通常只需要把标准版的结论“平移”一下，但平移的方式因游戏而异，不能无脑套。最稳的方法是重新打表找规律。

4. 威佐夫博弈：贝蒂定理与黄金分割的登场

4.1 两堆石子的新局面

威佐夫博弈（Wythoff Game）是两堆石子的取子游戏：有两堆石子，数量分别为a和b，两人轮流取，有两种操作方式：

1. 从其中一堆取任意多个（至少1个）。
2. 从两堆同时取相同数量的石子（至少1个）。

取到最后一个石子的人获胜。

这个游戏的状态是二维的(a, b)，假设a <= b。打表找必败态：

必败态序列：(0,0), (1,2), (3,5), (4,7), (6,10), (8,13), (9,15), ...

观察规律：每个必败态的差值b-a依次是0, 1, 2, 3, 4, 5, 6... 而且每个正整数恰好出现在一个必败态中（作为a或b）。

4.2 贝蒂定理：为什么必败态与黄金分割有关

设第k个必败态（从k=0开始）为(a_k, b_k)，其中a_k < b_k（k>=1）。根据观察，b_k - a_k = k。而且a_k是前面所有必败态中未出现的最小正整数。

这个序列有一个闭式解：a_k = floor(k * φ)，b_k = floor(k * φ^2)，其中φ = (1+√5)/2 ≈ 1.618是黄金分割比。

为什么？这要用到贝蒂定理（Beatty's Theorem）：如果两个正无理数α和β满足1/α + 1/β = 1，那么序列{floor(nα)}和{floor(nβ)}恰好划分正整数集（即每个正整数恰好出现在其中一个序列中）。

取α = φ，β = φ^2，验证1/φ + 1/φ^2 = 1（因为φ^2 = φ+1，所以1/φ + 1/φ^2 = (φ+1)/φ^2 = φ^2/φ^2 = 1）。所以{floor(kφ)}和{floor(kφ^2)}划分正整数集。

而威佐夫博弈的必败态恰好满足：a_k = floor(kφ)，b_k = a_k + k = floor(kφ) + k = floor(kφ + k) = floor(k(φ+1)) = floor(kφ^2)。所以必败态就是这两个序列配对。

这个证明的美妙之处在于：它把博弈论的必败态分布和数论中的无理数划分联系起来了。竞赛中遇到威佐夫博弈，直接判断：如果a = floor((b-a) * φ)，则是必败态，否则是必胜态。

4.3 精度问题：竞赛中的实现细节

用公式判断时，φ是无理数，浮点运算会有精度问题。当a和b很大时（比如10^18），double的精度不够。

解决方案：用整数运算模拟。设d = b - a，需要判断a是否等于floor(d * φ)。由于φ = (1+√5)/2，可以转化为判断a是否满足某个整数不等式。

具体做法：计算d * (1+√5)/2，但用整数运算。设x = floor(d * (1+√5)/2)，可以通过以下方式精确计算：

import math def wythoff(a, b): if a > b: a, b = b, a d = b - a # 用高精度计算 floor(d * (1+sqrt(5))/2) # 方法：用整数平方根 # floor(d * (1+sqrt(5))/2) = floor((d + d*sqrt(5))/2) # 先算 floor(d*sqrt(5))，再处理 # 更稳的方法：用decimal或直接比较 phi = (1 + math.sqrt(5)) / 2 return a == int(d * phi)

对于10^18级别的数据，double的精度大约15-16位十进制，可能出错。更稳的方法是：用整数运算判断a是否等于floor(d * φ)。由于φ满足φ^2 = φ + 1，可以推导出判断条件：

a = floor(d * φ) 等价于 a <= d * φ < a+1，即 a/d <= φ < (a+1)/d。由于φ是无理数，可以转化为整数比较：a^2 + a*d - d^2 的符号？实际上有更直接的结论：

必败态当且仅当 a = floor(d * φ)，等价于 a = floor((d * (1+√5))/2)。

在C++中，可以用long double（80位扩展精度，约18-19位十进制）来算，对于10^18的数据基本够用。如果还不放心，可以用整数二分或直接推导整数条件。

实操心得：威佐夫博弈的精度坑是经典问题。我见过有人在区域赛因为double精度不够WA了3发。建议直接用long double，或者记住一个整数判断法：设d = b-a，则必败态当且仅当 a == (long long)(d * 1.6180339887498948482)。这个常数写够20位，配合long double，10^18以内不会错。

5. 尼姆博弈与SG定理：从具体游戏到通用框架

5.1 尼姆博弈：异或和的魔力

尼姆博弈（Nim Game）是博弈论中最核心的模型：有n堆石子，每堆数量为a_i，两人轮流取，每次可以从任意一堆中取任意多个（至少1个），取到最后一个石子的人获胜。

结论：如果a_1 xor a_2 xor ... xor a_n = 0，则必败态；否则必胜态。

这个结论的证明分两步：

第一步：异或和为0时，任何操作都会使异或和非0。

假设当前异或和为0。从某一堆取走x个石子（x>=1），该堆从a变成a' = a-x < a。新的异或和 = 0 xor a xor a' = a xor a'。由于a' < a，所以a xor a' != 0（因为两个不同的数异或不可能为0）。所以操作后异或和非0。

第二步：异或和非0时，存在操作使异或和变为0。

设当前异或和为S != 0。找到S的最高位1，设该位为第k位。必然存在某一堆a_i，其第k位也是1（否则S的第k位不可能是1）。令a_i' = a_i xor S。由于a_i的第k位是1，S的第k位是1，所以a_i'的第k位是0，且a_i' < a_i（因为最高位变小了）。所以从第i堆取走a_i - a_i'个石子是合法操作。操作后，新的异或和 = S xor a_i xor a_i' = S xor a_i xor (a_i xor S) = 0。

两步合起来，结论成立。这个证明是构造性的，给出了必胜策略：每次找到异或和的最高位，选一堆该位为1的石子，把它变成a_i xor S。

5.2 SG函数：把任意游戏映射成尼姆堆

尼姆博弈的结论很漂亮，但它只适用于“从一堆取任意多个”这种操作。如果游戏规则变了，比如每次只能取1或2个，或者游戏是“分割”而不是“取子”，尼姆博弈的结论就不直接适用了。

SG函数（Sprague-Grundy函数）解决了这个问题。它的核心思想是：任何公平组合游戏的状态，都可以映射成一个非负整数，使得这个状态等价于一个大小为该整数的尼姆堆。

定义：对于一个状态x，SG(x) = mex{SG(y) | y是x的后继}，其中mex是最小非负整数（Minimum Excluded），即最小的不在集合中的非负整数。

有了SG函数，多个独立子游戏组合的局面，其SG值等于各子游戏SG值的异或和。如果异或和为0，则必败；否则必胜。

为什么？因为SG函数的定义保证了：

• 如果SG(x) = k，则x可以到达所有SG值为0,1,...,k-1的后继（由mex定义保证存在），且不能到达SG值为k的后继。
• 这与尼姆堆大小为k的行为完全一致：从大小为k的堆可以取到任意小于k的大小，但不能保持k不变。

所以SG函数把任意游戏“翻译”成了尼姆博弈。尼姆博弈的异或结论可以直接套用。

5.3 SG函数的计算：从打表到记忆化搜索

计算SG函数的标准方法是记忆化搜索：

def sg(x, memo, moves): if x in memo: return memo[x] reachable = set() for m in moves: if x >= m: reachable.add(sg(x - m, memo, moves)) g = 0 while g in reachable: g += 1 memo[x] = g return g

对于状态空间大的问题，需要找SG函数的规律。比如“每次取1到m个”的取子游戏，SG(x) = x mod (m+1)。这个规律可以用归纳法证明。

实操心得：SG函数的打表找规律是竞赛中的常规操作。我通常先写一个暴力SG，打印前100个值，然后观察周期性。大部分取子类游戏的SG函数都是周期性的，找到周期后就能O(1)计算。注意：周期可能不是从0开始的，前面可能有一段“前缀”，需要单独处理。

6. 反尼姆博弈：规则反转后的坑点

6.1 取到最后一个输的尼姆博弈

反尼姆博弈（Misère Nim）的规则是：取到最后一个石子的人输。其他规则和尼姆博弈一样。

结论比标准尼姆复杂：

• 如果所有堆的大小都是1，则必败态当且仅当堆数n是奇数（因为每堆1个，轮流取，取到最后一个的输，所以奇数堆时先手被迫取最后一个）。
• 如果存在至少一堆大小大于1，则必败态当且仅当异或和为0。

为什么？分情况讨论：

情况一：所有堆都是1。游戏变成n个1，每次只能取1个。总共取n次，第n次取的人输。所以n为奇数时先手输，n为偶数时先手赢。

情况二：至少有一堆大于1。此时结论和标准尼姆一样：异或和为0则必败。证明思路是：当异或和为0且至少有一堆大于1时，先手无论怎么取，都会破坏异或和为0的状态，对手可以恢复。而且对手可以控制游戏不进入“所有堆都是1”的必败分支。具体证明略复杂，但结论是可靠的。

6.2 反尼姆的常见错误

很多人以为反尼姆就是把标准尼姆的结论反过来，这是错的。反尼姆的结论是分情况的，不能简单反转。

我见过一个典型的错误：有人写反尼姆的判断时，直接判断异或和是否为0，忽略了“所有堆都是1”的特殊情况。结果遇到n=1, a=[1]的数据时，异或和为1，按标准尼姆是必胜，但反尼姆下先手必须取1个，取完对手面对0个，对手输了？等等，取到最后一个输，先手取走最后一个，先手输了。所以n=1, a=[1]是必败态。但异或和为1，按标准尼姆是必胜。所以确实不能简单套。

正确的判断逻辑：

def misere_nim(piles): xor_sum = 0 all_one = True for p in piles: xor_sum ^= p if p > 1: all_one = False if all_one: return len(piles) % 2 == 0 # 偶数堆必胜 else: return xor_sum != 0 # 异或和非0必胜

注意：反尼姆的结论只适用于“取到最后一个输”的尼姆博弈。如果游戏还有其他限制（比如每次最多取m个），结论会变，需要重新推导。

7. SG定理的进阶应用：分割游戏与图上游戏

7.1 分割游戏：SG函数的加法性质

有些游戏不是“取子”，而是“分割”。比如：有一张n*m的纸，每次可以沿格线剪开，剪成两块，谁不能剪谁输。这种游戏的状态是一个矩形，操作是把它分成两个矩形。

对于分割游戏，SG函数有一个重要性质：如果一次操作把状态x分成y和z两个独立子游戏，则SG(x) = mex{SG(y) xor SG(z)}。这是因为分割后的两个子游戏是独立的，可以分别计算SG值，再异或。

这个性质大大扩展了SG定理的适用范围。很多看起来复杂的游戏，只要能分解成独立子游戏，就能用SG定理处理。

7.2 图上游戏：SG函数在有向图上的计算

更一般地，游戏的状态转移可以构成一个有向无环图。每个节点是一个状态，每条边是一次操作。SG函数在这个图上定义：

SG(v) = mex{SG(u) | u是v的后继}

如果图有环，游戏可能无限进行，需要特殊处理（通常约定不能重复经过同一状态，或者游戏在有限步内强制结束）。

对于图上游戏，计算SG函数的方法和取子游戏一样：记忆化搜索或拓扑排序递推。如果图很大，需要找规律。

7.3 多子游戏组合：异或和的直观理解

为什么多个独立子游戏的SG值要异或？直观理解：每个子游戏相当于一个尼姆堆，堆的大小就是SG值。尼姆博弈的结论是异或和为0则必败，所以多个子游戏组合的胜负判断就是SG值异或和是否为0。

这个直观理解在竞赛中非常有用。遇到一个复杂游戏，先看能不能分解成独立子游戏，如果能，分别算SG值，再异或。

实操心得：分解子游戏时要注意“独立性”的定义。两个子游戏必须互不影响，即在一个子游戏中的操作不能改变另一个子游戏的状态。如果操作会同时影响多个子游戏，就不能简单分解，需要把整个局面作为一个状态来算SG。

8. 从打表到证明：博弈论题目的通用解题流程

8.1 第一步：判断游戏类型

拿到一道博弈论题目，先判断它属于哪类：

• 单堆取子，每次取1到m个：巴什博弈。
• 两堆取子，可以取一堆任意个或两堆相同个：威佐夫博弈。
• 多堆取子，每次取一堆任意个：尼姆博弈。
• 多堆取子，取到最后一个输：反尼姆博弈。
• 其他规则：可能需要SG函数或找规律。

8.2 第二步：小数据打表

如果无法直接套用已知模型，先写暴力DP或暴力SG，打印小数据的结果。打表时注意：

• 状态表示要清晰，比如(a, b)表示两堆数量。
• 转移要完整，不要漏掉任何合法操作。
• 打印格式要便于观察规律，比如按a排序，或者按差值排序。

8.3 第三步：观察规律并猜测公式

打表后观察N/P的分布。常见规律：

• 周期性：每隔k个状态重复一次。
• 线性关系：P态满足某个线性方程。
• 与数论函数相关：比如floor、mod、异或。

8.4 第四步：证明猜测

猜测需要证明才能放心使用。证明方法：

• 数学归纳法：证明P态满足某条件，N态满足另一条件。
• 构造性证明：给出必胜策略，证明策略可行。
• 反证法：假设存在不满足条件的P态，推出矛盾。

8.5 第五步：实现并测试

证明后实现代码，注意边界条件和精度问题。测试时至少覆盖：

• 最小数据（n=0, n=1）。
• 边界数据（n=m, n=m+1）。
• 大数据（验证公式是否溢出或精度不够）。

实操心得：博弈论题目的测试数据往往很刁钻，尤其是边界情况。我习惯在实现后手动构造几组边界数据，比如全1、全m、n=m+1等，确保代码不会在这些情况下出错。

9. 竞赛中的博弈论实战经验与避坑清单

9.1 常见坑点汇总

9.2 时间分配建议

博弈论题目在区域赛中通常属于“中等难度”题。如果一眼能看出是经典模型，直接套公式，5分钟内解决。如果需要打表找规律，预留20-30分钟。如果打表后找不到规律，考虑是否需要用SG函数或更复杂的数学工具。

9.3 训练建议

想提高博弈论水平，建议按以下顺序练习：

1. 先把巴什、威佐夫、尼姆、反尼姆四个经典模型的手推过程完整写一遍，不查资料。
2. 刷20道经典模型的直接应用题，确保公式记牢。
3. 刷10道变形题（Misère版本、多堆变种、取子规则变化），练习打表找规律。
4. 刷5道SG函数应用题（分割游戏、图上游戏），练习SG函数的计算和分解。
5. 刷5道综合题（多个子游戏组合、需要证明的题），练习完整解题流程。

9.4 个人体会

我刚开始学博弈论时，最大的误区是“背结论”。后来发现，背下来的结论只能解决原题，稍微变形就不会。真正有用的是推导能力：给定一个新游戏，能自己打表、找规律、证明、实现。这个能力不是靠背题能练出来的，必须亲手推几个模型，把“为什么”搞清楚。

另外，博弈论和数论、组合数学的联系非常紧密。威佐夫博弈用到贝蒂定理，尼姆博弈用到异或性质，SG函数用到mex和DAG。如果这些基础知识不牢，博弈论也很难学好。建议在学博弈论的同时，补一下数论和组合数学的基础。

最后，博弈论题目的代码通常很短，但思维量很大。竞赛中遇到博弈论题，不要急着写代码，先在纸上推一推，把规律找出来再写。磨刀不误砍柴工，这个习惯能帮你省下大量调试时间。