企业官网建设流程全解析

1. 为什么博弈论是算法竞赛里最“反直觉”的一类题

刚接触算法竞赛那会儿，我对博弈论题目的印象就两个字：玄学。明明规则简单到用一句话就能说清——两个人轮流取石子，谁取到最后一个谁赢——但真到写代码的时候，要么是状态推不出来，要么是推出来了却不知道怎么优化，要么是看了题解之后恍然大悟、过两天再遇到同类题又完全没思路。后来打得多了才慢慢意识到，博弈论不是靠灵光一现，它背后有一套非常严密的数学结构，只要把这套结构吃透，绝大多数竞赛博弈题都能归到有限的几个模型里。

这篇总结就是把我这些年刷博弈论题踩过的坑、总结出的模型、以及每个结论背后的证明推导，完整地梳理一遍。核心关键词包括Nim博弈、SG函数、Sprague-Grundy定理、P/N状态、反Nim、威佐夫博弈、巴什博弈等。内容会从最基础的必胜必败态定义讲起，一路推到SG定理的完整证明，再到各种变形题的拆解思路。适合已经会写基础搜索、但对博弈论一直似懂非懂的竞赛选手，也适合想系统补一下这部分知识的朋友。我不会只丢结论给你，每个结论我都会尽量把“为什么是这样”讲清楚，因为博弈论这东西，你不理解证明，遇到变形题就是抓瞎。

2. 从零建立博弈论的核心概念体系

2.1 公平组合游戏的定义与适用范围

博弈论题目在算法竞赛里绝大多数属于公平组合游戏（Impartial Combinatorial Game，简称ICG）。这个名词听起来唬人，但拆开看就三个条件：第一，两个玩家轮流操作，操作规则完全一样，不存在“你能这么走但我不能”的情况；第二，游戏状态有限，不存在无限循环（或者循环可以被判定为平局）；第三，无法操作的一方判负，也就是通常说的“不能走的人输”。

为什么先强调这个定义？因为很多新手拿到一道博弈题，上来就开始推状态，结果推了半天发现这游戏根本不是公平组合游戏——比如有的题里两个玩家能做的事不一样，那就不适用Nim和SG那一套，得用别的方法（比如对抗搜索或者策略分析）。所以判断一道题能不能用SG定理，第一步就是确认它是不是ICG。我个人的经验是，只要题目里出现“两个人轮流”“规则相同”“不能操作者输”这三个特征，基本就可以往ICG方向靠。

2.2 P状态与N状态：博弈论的最小分析单元

任何ICG的每个状态都可以被标记为两种之一：P状态（Previous player wins，即先手必败）和N状态（Next player wins，即先手必胜）。这两个概念是整个博弈论分析的基石。

判定规则非常简洁：

• 如果一个状态没有任何合法操作（终端状态），那当前玩家无法行动，判负，所以它是P状态。
• 如果一个状态存在至少一个合法操作能到达P状态，那当前玩家就可以走到那个P状态让对手面对必败局面，所以它是N状态。
• 如果一个状态的所有合法操作都只能到达N状态，那无论怎么走都会把必胜局面交给对手，所以它是P状态。

这三条规则其实是递归定义的，从终端状态往回推，可以确定所有状态的P/N属性。我习惯把它理解成“P状态是坑，谁面对谁输；N状态是安全区，谁面对谁赢”。这个理解虽然粗糙，但在做题时非常管用——你只需要判断当前状态能不能一步走到一个“坑”里就行。

注意：P/N状态的递归判定在状态空间小的时候可以直接用记忆化搜索实现，但状态空间一大就必须找规律或者用SG定理。这是后面所有内容要解决的问题。

2.3 用P/N状态分析一个最简单的例子

拿最经典的取石子游戏举例：一堆n个石子，每次可以取1到3个，取到最后一个的人赢。我们来手动推一下P/N状态。

n=0时，无法操作，P状态。n=1,2,3时，可以一次取完，走到n=0这个P状态，所以都是N状态。n=4时，无论取1、2还是3，都会分别到达n=3,2,1，全是N状态，所以n=4是P状态。n=5,6,7时，可以分别取到n=4，所以是N状态。n=8时，又只能到达N状态，所以是P状态。

规律很明显：n是4的倍数时是P状态，否则是N状态。这个规律背后的逻辑是“每轮两人合计可以控制取走4个”，先手面对4的倍数时，无论他取几个，后手都能补到4，最终先手面对0个石子输掉。这就是巴什博弈的核心思想，后面还会详细展开。

3. Nim博弈：从结论到证明的完整推导

3.1 Nim博弈的规则与结论

Nim博弈是ICG里最经典、最重要的模型。规则是：有若干堆石子，每堆有若干个，两人轮流从任意一堆中取走任意正数个石子（至少取一个），取到最后一个石子的人赢。

结论非常简洁：把所有堆的石子数做异或运算（XOR），如果结果非零，先手必胜；如果结果为零，先手必败。

我第一次看到这个结论的时候是完全懵的——为什么是异或？异或这个运算跟取石子有什么关系？后来看了证明才明白，这个结论不是拍脑袋想出来的，而是严格从P/N状态推导出来的。下面我把证明完整走一遍。

3.2 Nim博弈结论的严格证明

设所有堆石子数的异或和为S。我们证明两个命题：

命题一：S=0的状态是P状态。

首先，终端状态（所有堆都是0）显然S=0，且是P状态。现在假设某个S=0的状态存在合法操作，玩家从第i堆取走k个石子，使第i堆从a_i变成a_i‘（a_i’ < a_i）。由于操作前S=0，即a_1 XOR a_2 XOR ... XOR a_n = 0，操作后异或和变为S‘ = S XOR a_i XOR a_i’ = a_i XOR a_i‘。因为a_i ≠ a_i’，所以a_i XOR a_i‘ ≠ 0，即S’ ≠ 0。这说明从S=0的状态出发，任何操作都会到达S≠0的状态。

命题二：S≠0的状态是N状态。

我们需要证明从任意S≠0的状态，都存在一个合法操作能到达S=0的状态。设S的最高位（最左边的1）在第p位。因为S≠0，所以至少存在一堆石子a_i，它的第p位也是1（否则所有堆的第p位都是0，异或结果的第p位不可能是1）。我们令a_i‘ = a_i XOR S。由于a_i的第p位是1，S的第p位也是1，异或后第p位变成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。

两个命题合起来就证明了：S=0是P状态，S≠0是N状态。这个证明的精妙之处在于，它同时给出了“怎么走”的构造方法——找到异或和最高位对应的那堆，把它变成a_i XOR S即可。

3.3 Nim博弈的代码实现与实操细节

代码实现极其简单，但有几个细节容易翻车：

// Nim博弈核心代码 int xorSum = 0; for (int i = 0; i < n; i++) { xorSum ^= piles[i]; } if (xorSum != 0) { // 先手必胜 } else { // 先手必败 }

实操心得：很多人会问“如果先手必胜，第一步该怎么走”。根据上面的证明，找到异或和S的最高位p，然后找一堆第p位为1的石子，把它变成a_i XOR S。这个操作在需要输出方案的题目里经常考，别忘了。

还有一个常见坑：石子数可能是0的堆。0对异或和没有影响，所以可以忽略，但读入的时候别因为0导致数组越界或者逻辑错误。

4. SG函数与Sprague-Grundy定理：博弈论的“万能钥匙”

4.1 为什么需要SG函数

Nim博弈解决的是“多堆独立石子”的问题，但实际竞赛题里，游戏往往不是简单的取石子——可能是棋盘上移动棋子、可能是拆分游戏、可能是各种奇怪的规则。这时候就需要一个更通用的工具，把任意ICG映射成Nim博弈，这就是SG函数和Sprague-Grundy定理的作用。

SG函数的核心思想是：给每个状态赋一个非负整数值（叫做SG值），使得这个值在博弈意义上等价于一堆大小为SG值的Nim石子。如果多个独立子游戏组合在一起，总SG值就是各子游戏SG值的异或和。这样，任意ICG都可以转化为Nim博弈来判定。

4.2 SG函数的定义与计算方法

对于一个状态x，它的SG值定义为：mex{SG(y) | y是x能一步到达的状态}，其中mex表示“最小的不在集合中的非负整数”。

举个例子：如果状态x能到达的状态SG值分别是{0, 1, 3}，那么SG(x) = mex{0,1,3} = 2。如果x是终端状态（没有后继），SG(x) = mex{空集} = 0。

计算SG值通常用记忆化搜索：

int sg[MAXN]; bool visited[MAXN]; int computeSG(int state) { if (sg[state] != -1) return sg[state]; set<int> reachable; for (每个从state能到达的状态next) { reachable.insert(computeSG(next)); } int g = 0; while (reachable.count(g)) g++; return sg[state] = g; }

注意：SG值的计算复杂度取决于状态数和每个状态的转移数。如果状态空间太大，就需要找SG值的规律（通常是周期性的），而不是暴力计算。

4.3 Sprague-Grundy定理的完整证明

SG定理的内容是：如果一个游戏由k个独立的子游戏组成，每个子游戏的SG值分别是g_1, g_2, ..., g_k，那么总游戏的SG值等于g_1 XOR g_2 XOR ... XOR g_k。当且仅当总SG值非零时先手必胜。

证明分两步，和Nim博弈的证明结构完全一样：

第一步：证明总SG=0时是P状态。假设总SG=0，玩家对第i个子游戏操作，使其SG从g_i变为g_i‘（g_i’ ≠ g_i）。新的总SG = 0 XOR g_i XOR g_i‘ = g_i XOR g_i’ ≠ 0。所以从总SG=0出发，任何操作都会到达总SG≠0。

第二步：证明总SG≠0时是N状态。设总SG=S≠0，最高位为p。存在某个g_i的第p位为1。令g_i‘ = g_i XOR S，则g_i’ < g_i。由于SG函数的定义，g_i‘一定在状态i的某个后继状态的SG值集合中（这是SG函数mex性质保证的），所以存在一个合法操作把第i个子游戏变成SG值为g_i’的状态。操作后总SG = S XOR g_i XOR g_i‘ = 0。

这个证明的关键在于SG函数的mex定义保证了“任何小于当前SG值的非负整数都能被某个后继状态达到”，这正是Nim博弈里“可以取任意数量石子”的推广。

4.4 SG定理在组合游戏中的实战应用

SG定理最强大的地方在于，它允许我们把一个复杂游戏拆成多个独立部分分别计算SG值，然后异或起来。比如经典的“Nim游戏变种：每次可以取1到k个石子”，单堆的SG值就是石子数mod (k+1)，多堆异或即可。

再比如“棋子移动游戏”：棋盘上有若干棋子，每次可以把一个棋子向左移动若干格，不能移动者输。每个棋子是独立的子游戏，分别算SG值再异或。这种拆分思想是SG定理的精髓，也是竞赛题最常考的形式。

实操心得：判断一个游戏能不能用SG定理，关键看子游戏之间是否真正独立——即对一个子游戏的操作不影响其他子游戏的SG值。如果存在相互影响，就不能简单异或，需要把相互影响的部分合并成一个子游戏来处理。

5. 经典博弈模型拆解与变形题分析

5.1 巴什博弈：最简单的“控制周期”模型

巴什博弈的规则是：一堆n个石子，每次取1到m个，取到最后一个者赢。结论是：n mod (m+1) ≠ 0时先手必胜，否则先手必败。

证明思路是“周期控制”：如果n是(m+1)的倍数，无论先手取k个，后手取(m+1-k)个，每轮合计取走m+1个，最终先手面对0个。如果n不是(m+1)的倍数，先手先取n mod (m+1)个，把局面变成(m+1)的倍数交给后手，然后模仿后手的操作保持周期。

巴什博弈的变形很多，比如“取到最后一个者输”（反巴什），这时候结论变成：n mod (m+1) ≠ 1时先手必胜。推导方法是把“取到最后一个输”转化为“取到倒数第二个赢”，相当于石子数减1的普通巴什。

5.2 威佐夫博弈：两堆石子的黄金分割

威佐夫博弈的规则是：两堆石子，每次可以从一堆取任意个，或者从两堆取相同个，取到最后一个者赢。结论涉及黄金分割比：设两堆中较少的是a，较多的是b，令k = b - a，如果a = floor(k × (1+√5)/2)，则先手必败，否则先手必胜。

这个结论的证明需要用到Beatty定理，竞赛中一般直接记结论。但理解它的几何意义很有帮助：必败态(a_k, b_k)满足a_k = floor(k×φ)，b_k = a_k + k，其中φ是黄金分割比。这些点构成了一条斜率约为1.618的直线上的整数点。

实操心得：威佐夫博弈的精度问题是个大坑。计算k×φ时浮点误差可能导致判定错误，建议用整数运算或者高精度。我一般用long double并把φ写成(1.0+sqrt(5.0))/2，实测在k不太大时没问题，但k超过10^9就要小心。

5.3 反Nim博弈：结论反转的经典案例

反Nim博弈的规则和Nim一样，但取到最后一个石子的人输。结论比普通Nim复杂：

• 如果所有堆都是1，则堆数为奇数时先手必败，偶数时先手必胜。
• 如果至少有一堆大于1，则异或和非零时先手必胜，异或和为零时先手必败。

为什么会有这个区别？因为当所有堆都是1时，游戏变成了“轮流取一个”，胜负完全由堆数奇偶决定。而当有堆大于1时，玩家可以通过控制局面避免被迫取最后一个，此时异或和的判定依然有效。

这个结论我第一次看到时觉得很反直觉——为什么全是1的时候规则不一样？后来画了几个状态图才明白，全是1的时候不存在“取一部分留一部分”的操作空间，所有操作都是确定的，所以P/N状态退化成奇偶判定。

5.4 阶梯Nim与树上博弈的转化技巧

阶梯Nim的规则是：石子放在阶梯上，每次可以把某一阶的石子往下移任意个到下一阶，移到地面（第0阶）的石子出局，不能移动者输。结论是：只需要考虑奇数阶上的石子，做异或和即可。

这个结论的证明用到了“配对”思想：偶数阶的石子可以被对手“镜像”操作抵消掉。具体来说，如果先手移动偶数阶的石子到奇数阶，后手可以把同样多的石子从那个奇数阶移到下一个偶数阶，保持奇数阶异或和不变。所以偶数阶的石子不影响胜负。

树上博弈是另一个常见变形：棋子在一棵树上，每次可以把一个棋子向根方向移动任意步。每个棋子是独立的子游戏，SG值等于该节点到根的距离。多个棋子异或即可。

6. 博弈论题目的常见坑与排查技巧

6.1 状态定义错误导致的连锁反应

博弈论题最容易翻车的地方就是状态定义。我见过太多人（包括我自己）因为状态定义少考虑了一个维度，导致整个SG值算错。比如“取石子+翻转硬币”的题，状态不仅要记录石子数，还要记录硬币朝向；再比如“棋盘上多个棋子”的题，如果棋子之间有相互限制，就不能简单拆分。

排查方法：拿小规模数据手推P/N状态，和代码输出对比。如果对不上，先检查状态定义是否完整，再检查转移是否遗漏。

6.2 SG值周期性的发现与验证

很多题的SG值有周期性，但周期不一定从0开始，也不一定是你猜的那个。我的一般流程是：先暴力算前100到200个SG值，观察规律；如果看不出明显周期，就写个程序自动找周期（从某个起点开始，连续两个周期完全一致）。

注意：找周期时一定要验证多个周期，避免巧合。我踩过的坑是只验证了一个周期就下结论，结果周期找错了，WA到怀疑人生。

6.3 边界条件与特殊情况的处理

博弈论题的边界条件特别多：石子数为0、堆数为1、所有堆都是1、先手第一步无路可走等等。这些情况往往需要单独处理，不能指望通用逻辑覆盖。

我的习惯是在代码里加一个special_case()函数，把所有能想到的特殊情况先判掉，再走通用逻辑。虽然看起来笨，但能避免很多莫名其妙的WA。

6.4 常见问题速查表

7. 从竞赛到实战：博弈论思维的迁移价值

博弈论在算法竞赛里是一个相对独立的模块，但它培养的思维方式其实很通用。P/N状态的递归判定本质上是一种逆向归纳——从终局倒推，判断每个局面的优劣。这种思维在决策分析、策略规划里都有应用。SG定理的拆分思想则是一种模块化分解——把复杂问题拆成独立子问题，分别求解再组合。这种思路在系统设计、项目管理里同样常见。

我自己在做一些策略类项目的时候，就经常用P/N状态的思路来分析“当前局面有没有必胜策略”。虽然实际问题往往比ICG复杂得多（存在信息不对称、非零和、连续决策等），但把能拆的部分拆开、能判定的部分先判定，这个方法论是通用的。

最后分享一个我刷博弈论题的小习惯：每做完一道题，我都会问自己三个问题——这道题的核心模型是什么？结论是怎么证明的？如果改一个规则，结论会怎么变？这三个问题能帮我把一道题吃透，而不是做完就忘。博弈论这东西，模型就那么几个，但变形无穷无尽，只有理解了证明，才能在变形题面前不慌。