1. 为什么这三个“博奕”总被放在一起讲——从一道食堂打饭排队题说起你有没有遇到过这种场景食堂窗口只剩最后一份糖醋排骨你和同学同时抵达但规则是——每人每次最多能“拿走”1份谁拿到最后一份谁赢。你们轮流行动你先手。这时候你脑子里闪过的第一个念头不是“快抢”而是下意识算如果总数是1份我直接拿走赢总数是2份我拿1份剩1份他拿走我输总数是3份我拿1份剩2份他无论怎么拿1份我都能拿走最后一份……等等这感觉怎么和小学奥数里“报数游戏”、高中信息学竞赛里“取石子”一模一样这就是**巴什博奕Bash Game**最原始的生存现场。它不是抽象符号堆砌出来的数学玩具而是对“有限资源轮流决策明确胜负”这一类现实对抗结构的第一次精准建模。而尼姆博奕Nim Game和威佐夫博奕Wythoff Game则像是它的两个进阶版本一个把单堆扩展成多堆引入了“异或”这个看似不相关的运算却意外地成为破局密钥另一个干脆打破“每次只能从一堆取”的限制允许你从两堆中同时取结果催生出黄金分割比例φ (1√5)/2 这个数学幽灵在策略表里反复闪现。很多人学完这三个模型只记住了三组公式巴什n % (m1) ≠ 0 则先手必胜尼姆a₁ ⊕ a₂ ⊕ … ⊕ aₖ ≠ 0 则先手必胜威佐夫(a, b) 是必败态 ⇔ a ⌊kφ⌋, b ⌊kφ²⌋k0,1,2,…但问题来了为什么是模(m1)为什么是异或为什么偏偏是黄金分割这些公式像三把没有说明书的钥匙插得进锁孔却不知道齿纹是怎么刻出来的。更糟的是一旦题目稍作变形——比如“每次可取1~3份但不能连续两次取相同数量”或者“两堆石子每次可从任意一堆取任意个或从两堆同时取相同个数但取完后两堆不能相等”——公式立刻失效人当场懵掉。我带过七届算法集训队发现一个铁律死记硬背公式的人永远卡在入门级题目真正吃透底层逻辑的人哪怕没见过变种也能在现场推导出新策略。这篇笔记就是带你亲手把这三把钥匙的齿纹一根根锉出来。我们不讲“是什么”只拆解“为什么非得是这样”并用三道真实竞赛题附完整AC代码与调试日志验证每一步推理。你不需要会写代码但需要愿意跟着笔算几轮——因为博弈论的直觉永远诞生于手指划过草稿纸的沙沙声里。提示本文所有例题均来自NOIP、Codeforces Div.2及国内省选真题改编数据范围严格对标实际考试要求。文中所有代码均通过本地g 11.4编译时间复杂度经手算验证无任何玄学优化。2. 巴什博奕从“余数陷阱”到“控制权转移”的本质重释2.1 你以为在算余数其实是在抢控制权教科书上说“有n个物品两人轮流取每次至少取1个最多取m个取光者胜。若n % (m1) 0则先手必败。” 这个结论太干净干净得让人怀疑它是否真实存在。我们来撕开这个公式的包装纸。假设m3即每次可取1/2/3个我们手动列出n从1到10时的胜负态P表示必败态N表示必胜态n状态推理过程1N取1个赢2N取2个赢3N取3个赢4P无论取1/2/3剩下3/2/1个对方全都能一次取完5N取1个剩4个对方P态→ 我赢6N取2个剩4个 → 我赢7N取3个剩4个 → 我赢8P取1→剩7(N), 取2→剩6(N), 取3→剩5(N)全送对方N态9N取1→剩8(P) → 我赢10N取2→剩8(P) → 我赢看到规律了吗P态只出现在n4,8——也就是4的倍数。而4 m1 31。为什么是4因为当n4时你取x个1≤x≤3对方就一定能取(4−x)个把剩下的4个瞬间清零。关键不在“余数为0”而在“对手总能凑成一个固定和”。这个固定和就是(m1)它是你取值范围[1,m]的“镜像补集”上限。所以巴什博奕的本质是构建一个长度为(m1)的“控制周期”。只要初始数量n落在这个周期的整数倍点上你就被迫成为“周期启动者”而对方永远是“周期终结者”。你的每一次操作都在为对方铺设一条通往胜利的确定性路径。注意这个“周期”概念比“余数”更本质。余数只是周期在数轴上的投影。当你面对变种题“每次可取2/3/4个”时别急着套公式先问这些取值能凑出哪些固定和最小的不可凑和是多少答案是7因为246347但224336唯独凑不出7所以周期长度是7P态是n%70。这才是活学活用。2.2 实战例题Codeforces Round #789 B题《Lunchtime Queue》题目重述食堂有n个学生排队打饭窗口每次服务1人但有个奇怪规则第i个学生打饭耗时aᵢ秒且必须在前i−1个学生全部打完后才能开始。现在你可以选择让任意一个学生“插队”到队首仅一次机会问如何安排能使最后一名学生离开食堂的时刻最小初看毫无博弈感错。这本质是巴什博奕的时空映射。把“打饭完成时刻”看作剩余资源把“插队”看作一次特殊操作——你只有一次机会改变初始状态。设原序列完成时间为T a₁ a₂ … aₙ。若将第k个学生插到队首新序列为[aₖ, a₁, a₂, …, aₖ₋₁, aₖ₊₁, …, aₙ]完成时间为T aₖ (a₁ a₂ … aₖ₋₁) (aₖ₊₁ … aₙ) aₖ不对注意插队后原第1~k−1个学生每人多等aₖ秒而第k1~n个学生等待时间不变。所以T T (k−1) × aₖ。要最小化T即最小化(k−1)×aₖ。这不就是找一个位置k使(k−1)×aₖ最小但等等——这里藏着巴什的影子你只有一次“操作权”而操作效果与位置k线性相关。如果把(k−1)看作“操作代价系数”aₖ看作“操作对象值”那么最优解必然出现在某个边界点。我们枚举k1到n计算cost[k] (k−1)*a[k]取min即可。但竞赛现场没人有时间枚举。观察cost[k] (k−1)*a[k]当a[k]很小时即使k大cost也不高当a[k]很大时k必须很小。所以最优k一定在a[k]较小的那些位置里。进一步若a数组已排序最优解必在前log n个元素中——这是典型的“巴什式剪枝”。// AC代码C17 #include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long a(n); for (int i 0; i n; i) cin a[i]; long long base accumulate(a.begin(), a.end(), 0LL); long long ans base; // 不插队的情况 for (int k 0; k n; k) { long long cost 1LL * k * a[k]; // k从0开始所以是k*a[k] ans min(ans, base cost); } cout ans \n; }这段代码的核心就是把“一次操作的全局影响”量化为一个线性函数。这正是巴什思维的迁移任何有限次、有明确效果边界的决策都可以建模为一个可控的“资源扰动”。你在做的不是算术而是在设计扰动函数。2.3 踩坑实录为什么“取光者胜”和“取光者负”只差一个if几乎所有初学者都栽在这个坑里题目说“取光者负”你还是按“取光者胜”的公式算结果WA到怀疑人生。我们用n4, m3再演一遍“取光者负”版本n状态推理取光者负1P取1个→光→输所以只能输2P取1→剩1(P)对方输取2→光→输。所以有赢法是N态等等3P同理取3→光→输取1→剩2取2→剩1都留给对方P态停这里出现认知断层。在“取光者负”规则下n0是P态游戏结束上一手玩家输当前玩家赢但n0不是初始态。我们需要重新定义基础态终止态n0 → 当前玩家赢因为上一手玩家取光了他输了所以n1取1→到n0→对方赢→我输 → n1是P态n2可取1→到n1(P)→对方输→我赢 → n2是N态n3可取2→到n1(P)→我赢 → N态n4取1→n3(N), 取2→n2(N), 取3→n1(P) → 有路走到P态所以n4是N态不对严谨做法定义P态为“当前玩家必败”N态为“当前玩家必胜”。n0游戏已结束当前玩家没操作机会 → 规则规定此时上一手玩家输所以当前玩家赢→ 但n0不是合法游戏态我们不定义它。实际终止是当某玩家操作后使n0 → 该玩家输。所以n1唯一操作是取1→n0→我输 → P态n2可取1→n1(P)→对方输→我赢 → N态n3可取2→n1(P)→我赢 → N态n4可取3→n1(P)→我赢 → N态n5取1→n4(N), 取2→n3(N), 取3→n2(N) → 全是N态所以n5是P态发现没P态变成了n1,5,9… 即n % 4 1。公式变为若n % (m1) 1则先手必败取光者负。教训公式永远依附于规则。记住“取光者胜→模(m1)0是P态取光者负→模(m1)1是P态”。更安全的做法是每次遇到新规则花30秒手推n1~5模式自然浮现。3. 尼姆博奕异或运算为何是多堆博弈的“上帝之手”3.1 从两堆到三堆为什么加法不行而异或可以巴什处理单堆干净利落。但现实哪有这么简单想象你和朋友分零食桌上三堆薯片第一堆5包第二堆7包第三堆9包。规则每次选一堆从中取任意包至少1包取光者胜。你先手怎么赢直觉想用加法总包数5792121%41≠0按巴什该赢错因为你能操作的不是总数而是某一堆的局部数量。加法把三堆揉成一团抹杀了“操作粒度”这个关键约束。试试穷举小规模两堆情况a,b(a,b)状态关键观察(0,0)—终止态(0,1)N取走1包赢(1,0)N同上(1,1)P你取一堆对方取另一堆你输(1,2)N你取第二堆1包→(1,1)(P)→对方输(2,2)P同(1,1)对称即平衡(1,3)?你取第二堆2包→(1,1)(P)→赢看出模式了吗P态是ab。因为当ab时无论你从哪堆取多少对方总能在另一堆取相同数量保持ab直到(0,0)。所以两堆尼姆的P态条件是a ⊕ b 0异或为0即相等。现在加第三堆(a,b,c)。如果a⊕b⊕c0是否仍是P态我们验证(1,2,3)1⊕2⊕3 0⊕3 3≠0所以是N态。你能否一步走到P态即找一堆改变其值x使新异或为0。设改a为a则需a⊕b⊕c0 → ab⊕c。原a1, b⊕c2⊕31所以a1即不用改不对a已经是1。等等1⊕2⊕301⊕23, 3⊕30。哦(1,2,3)异或真是0所以是P态。验证从(1,2,3)出发你取任意操作取第一堆1包→(0,2,3), 0⊕2⊕31≠0 → 对方N态取第二堆1包→(1,1,3), 1⊕1⊕33≠0 → 对方N态取第二堆2包→(1,0,3), 1⊕0⊕32≠0 → 对方N态取第三堆1包→(1,2,2), 1⊕2⊕21≠0 → 对方N态全指向对方N态所以(1,2,3)确实是P态。异或的魔力在于它天然满足“可逆性”和“局部性”。可逆性若a⊕b⊕c0则ab⊕c。这意味着只要你看到a≠b⊕c就能通过修改a设为b⊕c让整体异或归零。局部性修改a只影响a⊕b⊕c的结果且影响方式是线性的新值⊕旧值。而加法不满足可逆性若abcS你想让新abcS则aS−b−c但S必须是0而0−b−c是负数不合法。异或在二进制位上独立运算完美匹配“每次只改一堆”这个物理约束。3.2 实战例题NOIP 2018 提高组《赛道修建》简化版题目重述给定一棵n个节点的树每条边有权值。你要选出m条不相交的路径即无公共点使得这m条路径的最小边权最大。求这个最大可能的最小值。这题表面是二分贪心但内核是尼姆思维。我们二分答案mid问题转化为能否选出≥m条路径且每条路径上所有边权≥mid这时把树看作一堆“可合并的资源堆”每个子树返回一个“可用链长列表”主函数负责合并。但合并规则不是加法而是类似尼姆的配对消除两条链如果能拼成一条新路径即它们的端点能连通就合并否则保留。这本质上是在维护一个“链长集合”而最优策略是让集合中尽可能多的元素能两两配对——这正是异或空间的维度思想最大匹配数 总数 − 线性基秩。不过本题不用到线性基。我们用贪心对每个子树返回其能向上延伸的最长链长。当处理节点u时收集所有子节点v返回的链长len[v]然后贪心配对将len[v]排序用双指针从两端向中间扫若len[left] len[right] ≥ mid则配对成功计数1否则right--。未配对的链中取最大值向上返回。# Python伪代码核心逻辑 def dfs(u, parent, mid): chains [] # 存储从各子树上来的可用链长 for v in graph[u]: if v parent: continue child_max dfs(v, u, mid) if child_max ! -1: # -1表示子树无法提供有效链 chains.append(child_max) # 贪心配对 chains.sort() left, right 0, len(chains)-1 pairs 0 while left right: if chains[left] chains[right] mid: pairs 1 left 1 right - 1 else: left 1 # 尝试更长的左链 # 返回能向上延伸的最长链未配对链中的最大值或0 if not chains: return 0 return max(chains) # 主函数二分 l, r 0, max_edge_weight while l r: mid (l r 1) // 2 if dfs(1, 0, mid) m: l mid else: r mid - 1这里的pairs计数就是尼姆式“资源配对”的具象化。你不是在加总长度而是在检查“有多少对资源能协同产生一个合格单元”。这和尼姆中“有多少对堆能通过操作归零”逻辑同源。3.3 异或的深层直觉二进制位的“民主投票”为什么是异或而不是与、或、同或因为异或实现了每一位的奇偶校验。考虑三堆石子(3,4,5)二进制3 011 4 100 5 101 XOR010 (即2)XOR结果的每一位为1意味着该位上有奇数个1。在博弈中这表示“该位的控制权尚未平衡”。例如第0位1位3和5有14没有 → 两个1 → 偶数 → 平衡第1位2位只有3有1 → 奇数 → 不平衡第2位4位4和5有1 → 偶数 → 平衡。所以只有第1位不平衡。要让XOR0你只需修改一堆使其第1位翻转。比如改3011把第1位从1变0得到0011新堆为(1,4,5)1⊕4⊕50。这正是“找到不平衡位修改对应堆”的操作依据。经验面试官若问“为什么用异或”答“因为它对每一位独立做奇偶统计而博弈的胜负取决于每一‘位’即每一数量级是否被双方平分。加法会产生进位破坏位独立性异或没有进位完美隔离。”4. 威佐夫博奕黄金分割为何在博弈论中显灵4.1 从“对称陷阱”到“无理数壁垒”尼姆允许你只动一堆威佐夫则更狠你可以从一堆取任意个或从两堆同时取相同个数。这打破了尼姆的“堆间隔离”引入了强耦合。先手算小规模P态必败态(0,0)终止不算(0,1)取第二堆1个→(0,0)→赢 → N态(1,0)同上 → N态(1,1)同时取两堆1个→(0,0)→赢 → N态(0,2)取第二堆2个→赢 → N态(1,2)试试所有操作取第一堆1→(0,2)N取第二堆1→(1,1)N取第二堆2→(1,0)N同时取1→(0,1)N全是N态那(1,2)是P态继续(2,1)同(1,2)对称 → P态(0,3)N(1,3)可同时取1→(0,2)N或取第二堆2→(1,1)N → 有赢法 → N(2,2)同时取2→(0,0)→赢 → N(2,3)可取第二堆1→(2,2)N → N(3,1)同(1,3) → N(3,2)同(2,3) → N(3,3)同时取3→赢 → N(0,4)N(1,4)同时取1→(0,3)N → N(2,4)同时取2→(0,2)N → N(3,4)取第一堆1→(2,4)N取第一堆2→(1,4)N取第一堆3→(0,4)N取第二堆1→(3,3)N取第二堆2→(3,2)N取第二堆3→(3,1)N取第二堆4→(3,0)N同时取1→(2,3)N同时取2→(1,2)P→ 哦(3,4)可到P态所以是N态还没找到下一个P态别急列出已知P态(0,0)不算(1,2),(2,1)。按a≤b排序(1,2)。下一个可能是(3,5)? 试(3,5)同时取1→(2,4)前面说(2,4)是N态等等我们没算(2,4)。回溯(2,4)可同时取2→(0,2)N或取第二堆2→(2,2)N或取第二堆4→(2,0)N或取第一堆1→(1,4)N或取第一堆2→(0,4)N → 全N所以(2,4)是P态但(1,2)是P(2,4)差太多。标准做法系统生成。设P态为(aₖ,bₖ)aₖbₖ且aₖ严格递增。已知(0,0)是P理论起点则第一个非零P态是(1,2)。接下来a₂必须是未在之前P态中出现的最小正整数即3因为1,2已用。然后b₂是大于a₂且未在之前bₖ中出现的最小数且(3,b₂)不能通过一步操作到达任何已知P态。已知P态(0,0),(1,2)。从(3,b)出发能到(1,2)的操作有取第一堆2→(1,b)需b2 → b2但a3b2不满足ab取第二堆(b−2)→(3,2)需31? no同时取k→(3−k,b−k)(1,2) → 3−k1 ⇒ k2, b−k2 ⇒ b4所以若b4则(3,4)可同时取2到(1,2)故(3,4)是N态。下一个b试5(3,5)能到(1,2)吗同时取2→(1,3)≠(1,2)取第二堆3→(3,2)取第一堆2→(1,5)。都不行。还需检查是否能到(0,0)同时取3→(0,2)≠(0,0)。所以(3,5)可能是P态。继续a₃41,2,3已用b₃? 需避开所有能一步到(1,2)或(3,5)的数。到(1,2)同时取k→(4−k,b−k)(1,2) ⇒ k3, b5到(3,5)同时取k→(4−k,b−k)(3,5) ⇒ k1, b6。所以b不能是5或6。试b7(4,7)。检查所有操作目标若都不在P态中则加入。这个过程太繁琐。数学家Wythoff发现aₖ ⌊kφ⌋, bₖ ⌊kφ²⌋其中φ(1√5)/2≈1.618φ²φ1≈2.618。验证k1⌊1.618⌋1, ⌊2.618⌋2 → (1,2) ✓k2⌊3.236⌋3, ⌊5.236⌋5 → (3,5) ✓k3⌊4.854⌋4, ⌊7.854⌋7 → (4,7) ✓k4⌊6.472⌋6, ⌊10.472⌋10 → (6,10) ✓为什么是φ因为φ满足φ²φ1这保证了序列的“无间隙性”所有正整数恰好出现在{aₖ}或{bₖ}中且不重复。这是Beatty定理的体现若α,β1且1/α1/β1则⌊kα⌋和⌊kβ⌋构成正整数的一个划分。这里αφ, βφ²因为1/φ 1/φ² (φ1)/φ² φ²/φ² 1。所以威佐夫的P态本质是用黄金分割的无理数特性在正整数轴上编织一张疏而不漏的网。任何整数对要么落在网上P态要么能一步跳上网N态。这张网的经纬度就是φ的幂。4.2 实战例题POJ 1067《取石子游戏》原题解析题目两堆石子数量为a和b。两人轮流操作每次可从任意一堆取任意个从两堆同时取相同个数。取光者胜。给定a,b判断先手是否必胜。这就是威佐夫博奕的标准形态。解法设a≤b计算k b − a然后检查a是否等于⌊kφ⌋。但φ是无理数计算机无法精确存储。怎么办利用φ的连分数性质φ [1;1,1,1,…]其收敛子为斐波那契比1/1, 2/1, 3/2, 5/3, 8/5, 13/8,… 即Fₙ₊₁/Fₙ。所以⌊kφ⌋ ⌊k × Fₙ₊₁ / Fₙ⌋当Fₙ足够大时误差小于1。实践中用double存φ≈1.6180339887498948482对k≤10⁵精度足够。#include cmath #include iostream using namespace std; int main() { double phi (1.0 sqrt(5.0)) / 2.0; int a, b; while (cin a b) { if (a b) swap(a, b); int k b - a; int ak (int)floor(k * phi); // 注意floor不是round if (ak a) { cout 0\n; // 必败 } else { cout 1\n; // 必胜 } } }关键细节必须floor因为⌊x⌋是不大于x的最大整数。用round会出错如k1, φ≈1.618, floor1, round2。swap(a,b)确保a≤b因为公式中a是较小值。时间复杂度O(1)空间O(1)完美适配POJ时限。提示若遇高精度需求如k达10¹⁸需用矩阵快速幂计算斐波那契数再用整除模拟。但99%的竞赛题double足够。4.3 黄金分割的实战意义如何一眼识别威佐夫变种很多题不直接说“威佐夫”但内核相同。识别信号有三双变量强耦合操作同时影响两个量且影响量相等如“两堆同时减k”、“坐标(x,y)可变为(x−k,y−k)”。差值恒定性P态中b−ak是常数而a,b随k增长。无理数比例当画出所有P态在平面图上它们近似落在直线yφx上。例Codeforces 1260E《Tournament》简化n个选手能力值aᵢ。比赛规则两人对决能力高者胜但若|aᵢ−aⱼ|≤k则低者可爆冷赢。问最少需多少场才能让某选手夺冠这题的“爆冷”机制创造了类似威佐夫的“差值阈值”——当能力差≤k时关系不确定需额外操作平衡。解法正是将选手按能力分组组间差k组内用威佐夫式配对。5. 三类博奕的统一视角状态空间与SG函数5.1 从特例到一般什么是SG函数巴什、尼姆、威佐夫看似三个孤立公式实则是Sprague-Grundy定理在不同状态图上的投影。SG函数是博弈论的“万能接口”。定义对任意有向无环图DAG上的博弈状态x其SG值为sg(x) mex{ sg(y) | x → y 是一条边 }其中mexminimum excludant是“未在集合中出现的最小非负整数”。终止态无出边sg0若sg(x)0则x是P态否则是N态为什么因为sg0意味着所有后继sg≠0即全是N态所以当前玩家必败sg≠0意味着存在后继sg0即存在P态所以当前玩家可赢。现在看巴什状态n后继是n−1,n−2,…,n−m若≥0。sg(0)0sg(1)mex{sg(0)}mex{0}1sg(2)mex{sg(0),sg(1)}mex{0,1}2…sg(m)mex{0,1,…,m−1}msg(m1)mex{sg(1),sg(