Nim博弈全解析：异或判定原理、构造技巧与SG函数扩展

很多人第一次接触Nim博弈都是从一句看似轻飘飘的话开始的把每堆石子的数量全部异或起来如果是0就先手必败否则先手必赢。我第一次听到这话时心里是抗拒的凭什么一个连加法都不是的运算能概括这么复杂的局面直到后来把递推表、二进制、必胜态必败态的定义全部过了一遍才真正明白这句话不是魔术而是组合博弈论里最漂亮的一组数学结论。这篇文章就把Nim博弈的模版思路、构造技巧和数学原理一次性讲透从最基础的规则到可以直接抄的代码再到各种变形题的判断方法希望给正在刷博弈专题或者做算法建模题的朋友省下我当年绕的那些弯路。1. 先把规则和直觉对齐Nim博弈到底在玩什么1.1 游戏规则与最后一步的直觉Nim博弈的规则其实特别简单桌上有若干堆石子每堆数量不一定要相等双方轮流走每一步只能从某一堆里取走任意正整数个石子可以一整堆全拿走谁取走最后一颗石子谁赢。没有平局没有随机性信息完全公开这就叫公平组合游戏。我第一次见到这个规则时直觉上觉得肯定要动态规划状态是每堆剩余数量的组合状态数爆炸根本没法做。后来才发现这种每一步只影响一个维度的结构天生就适合用数学工具收束而不是用DP硬扛。打个比方这就像你要判断一堆乱七八糟的果汁有没有毒与其一杯一杯去试还不如直接看配方表——Nim的配方表就是二进制。先从最小的情况找感觉只有一堆石子时先手直接全取走就赢了所以这是必胜局面。有两堆各1颗也就是(1,1)时先手无论取哪一堆后手都会取走另一颗所以(1,1)是先手必败。(1,2)呢先手可以把2那一堆取走一颗变成(1,1)把必败局面丢给后手所以(1,2)先手必胜。我当年就是靠一格格填这种小表慢慢建立起对局面性质而不是具体走法的敏感度。1.2 必败态是怎么定义的博弈题里最核心的概念是P态必败态Previous player winning即轮到走的人会输和N态必胜态Next player winning即轮到走的人能赢。判断一个局面是P还是N靠的是两条递推规则如果某个局面没有任何合法走法它就是P态如果一个局面存在一步走法能走到某个P态它就是N态如果一个局面的所有走法都只能走到N态那它就是P态。这套定义最厉害的地方在于它把所有战术都抛掉了只关心局面之间能不能一步到达的关系。你不需要枚举整局棋只需要判断当前局面属于哪一类。Nim博弈之所以能成为模版题正因为它的P/N态分布有极简的数学表达。理解这一点后面看异或结论就不会觉得是空降公式。很多新手一上来就背异或为0必败却不知道这个结论是怎么来的结果遇到反Nim、拆堆构造这类变体就完全不会变通而真正理解P/N态定义的人碰到任何新规则都能自己推一遍这才是模版背后的核心能力。2. 数学核心为什么判定条件是异或2.1 从二进制推演异或结论先直接给结论对于n堆石子数量分别为a1, a2, ..., an令s a1 XOR a2 XOR ... XOR an。如果s 0当前局面是P态轮到的人必败如果s ! 0当前局面是N态轮到的人必胜。为什么偏偏是异或关键在于两条性质。第一条从s0的局面走一步s一定变成非0。因为这一步只会改变一堆a_i把它变成a_i且0 a_i a_i那么这一堆的变化会让异或结果从0变成a_i XOR a_ia_i和a_i不相等这个值显然非0。第二条更关键从s!0的局面一定存在一步走法让新的异或变成0。设s的最高位是第k位必然存在某一堆a_j在第k位上是1。此时把a_j改成a_j a_j XOR s那么a_j一定小于a_j因为第k位从1变成0更高位的二进制位都不会改变整体数值必然变小而且所有堆异或起来正好是s XOR a_j XOR (a_j XOR s) 0完美归零。这两条性质合在一起正好满足了P/N态递推的全部要求从P态无论怎么走都只能进N态从N态至少有一条路能进P态。于是整个判定就自洽了。我第一次把这个证明完整写下来的时候真切体会到数学构造题的魅力一个看似复杂的博弈最终被一个布尔运算一句话概括。2.2 可以直接抄的模版代码有了上面的结论代码就变得非常直接。以最常见的要求判断先手胜负的题目为例#include bits/stdc.h using namespace std; int main() { int n; while (cin n) { long long xor_sum 0, x; for (int i 0; i n; i) { cin x; xor_sum ^ x; } if (xor_sum 0) cout Second win\n; else cout First win\n; } return 0; }这里有两个细节值得单独说明。第一用long long而不是int很多题石子数量会开到1e9甚至1e18int读入会直接溢出异或结果自然也是错的。第二while (cin n)处理多组数据这是OJ上最常见的输入格式漏掉这个循环会导致只处理一组数据就结束WA得莫名其妙。你可以把输出格式按题目要求改成先手/后手First/SecondYes/No等核心判定就这三行。2.3 把异或判定封装成模版函数刷题多了以后我习惯把博弈判断单独封装成函数方便在构造题里反复调用// 返回true表示当前局面是先手必败态(P态) bool isNimLose(const vectorlong long piles) { long long s 0; for (long long x : piles) s ^ x; return s 0; }真的别小看这种封装。构造题里你常常需要在取走若干石子后判断局面是否变成P态如果每次都临时写循环代码会越来越乱。封装之后你的注意力就能集中在怎么构造这一步上。我自己的模版文件里永远存着四样东西Nim判定、反Nim判定、SG函数、以及一个暴力对拍用的P/N表生成函数。后面几节会逐一展开这套组合几乎能覆盖百分之八十的公平组合游戏题。3. 构造题的思路怎么把局面改造成必败态3.1 构造题的本质找第一步很多Nim题不满足于判胜负而是反着问如果先手必胜请给出一种必胜的第一步或者给一堆限制条件让你构造一个无论后手怎么走都输的初始局面。这种题的本质就是利用上一节证明里的第二条性质从s ! 0出发找一堆a_j使得a_j a_j XOR s a_j然后把a_j改成a_j。实操步骤我总结成三步算全体石子的异或和s。找s的最高位最左边那个1所在的位置也就是找到任意一堆在第k位为1的堆。把这堆从a_j改成a_j XOR s取走的数量就是a_j - (a_j XOR s)。举个例子三堆石子是[3, 4, 5]换算成二进制301141005101异或结果是011 ^ 100 ^ 101 010也就是2。s2最高位是bit1。三堆里第1位是1的只有3这一堆所以改33 XOR 2 1也就是说把第一堆从3颗取到1颗取走2颗。改完后的局面是[1, 4, 5]再异或一次1 ^ 4 ^ 5 0正好变成必败态。整个构造过程只要会异或和比较大小手算都能完成实际比赛里我在草稿纸上推完再写代码基本一次过。3.2 两步走的构造拆分堆、添加堆与删除堆有些构造题不让你直接改一堆而是允许把一堆拆成两堆或者添加一堆/删除一堆。这时候异或视角依然好用。拆一堆a拆成b和cb c a且b、c为正整数局面的异或从s变成s ^ a ^ b ^ c。注意b ^ c不一定等于a所以拆分后的异或变化是s ^ a ^ b ^ c。要构造P态就要让s ^ a ^ b ^ c 0也就是b ^ c s ^ a同时还要满足b c a。这类题通常可以暴力枚举b从1到a-1因为b c a是强约束枚举量往往可控如果a特别大就要按二进制位思考怎么凑数本质是个带进位的按位构造问题。添加堆和删除堆更简单原来异或是s加一堆值v异或变成s ^ v要变成0就取v s删一堆a_i异或变成s ^ a_i要变成0就需要a_i s。所以删哪堆的答案往往直接就是那堆等于异或和的堆。这些结论不是死记的都是套异或性质现推出来的。写多了以后你会形成条件反射看到从当前局面出发走一步让对手必败第一反应永远是让总异或归零。3.3 构造题的边界处理构造题坑最密集的地方永远是边界。我踩过的几个点列一下异或和为0时说明当前局面已经是P态先手无论怎么走都会把N态交给对方。此时题目如果硬要你输出一步走法通常要输出-1或者某种约定值而不是随便构造一个看似合理的操作。改堆时一定要判断a_j XOR s a_j否则取走数量会变成负数逻辑直接炸这个判断也是你选第3.1节里那一堆的依据不能随便挑。石子数量范围很大时a_j - (a_j XOR s)用long long输出并注意题目要求的输出格式有的让输出堆编号有的让输出取走的数量有的两个都要。拆堆题里b和c都必须大于0枚举从1开始别写成0同时注意拆完之后堆数变了后续判断要用新的数组。这些边界在模版题里看起来微不足道但真实比赛里WA一次就要罚时二十分钟。我把它们写进自己模版的注释里每次用到都过一眼能省下大量无意义的返工。4. 从经典Nim走出去变形博弈与SG函数4.1 反Nim规则反转后的特殊处理反NimMisère Nim的规则是取走最后一颗石子的人输。很多人第一反应是把异或结论反过来就行这是最常见的错误。事实是如果所有堆的石子数都为1那么胜负由堆数的奇偶决定奇数堆时先手必败因为每次只能取1颗只要存在任何一堆大于1结论就和普通Nim完全一样异或非0则先手必胜。这个结论的推导其实不难关键是分两类讨论没有大于1的堆时是纯奇偶游戏有大于1的堆时先手总能通过一步把局面带进对方无法救回的状态P/N递推表可以验证。我把它整理成表格放进模版局面类型普通Nim判定反Nim判定不全为1 且 异或非0先手必胜先手必胜不全为1 且 异或为0先手必败先手必败全为1 且 堆数为奇数先手必胜先手必败全为1 且 堆数为偶数先手必败先手必胜这张表看着简单但如果没有提前整理现场推导很容易绕晕。特别是全为1的情况普通Nim和反Nim恰好相反这是最经典的陷阱。每次做题看到题面出现拿走最后一颗石子的人输这句话我都要先在草稿纸上把是否全为1的分支写清楚再动手。4.2 SG函数把Nim推广到一切公平组合游戏当游戏不是若干堆石子的形态而是棋盘、图上移动、卡片翻转这类结构时就需要SG函数出场了。SG函数定义在每一个局面上如果局面没有后继SG值为0否则SG值等于所有后继局面SG值集合的mex也就是最小未出现的非负整数。SG定理说如果整个游戏由若干独立子游戏组成那么总局面的SG值等于各子游戏SG值的异或。这其实就是Nim博弈的推广——一堆石子的SG值就是石子数本身整局游戏的SG值就是各堆SG值的异或于是又回到经典判定上。模板写起来也不复杂int sg[MAXN]; bool vis[MAXN]; // 每次递归前都要清空 int getSG(int state, vectorint moves) { if (sg[state] ! -1) return sg[state]; memset(vis, 0, sizeof(vis)); for (int m : moves) { if (state m) vis[getSG(state - m, moves)] 1; } for (int i 0; ; i) { if (!vis[i]) return sg[state] i; } }这里要注意vis数组在每一层递归前都要清零mex的查找一定要从0开始。如果状态空间特别大就要先打表找规律很多题的SG值是周期性的或者有简单的公式找到之后直接按结论写比硬算快得多。我见过不少选手在这类题上直接爆空间就是因为没做周期分析其实小数据跑一遍就能发现规律。4.3 常见变体速查除了反Nim和SG函数Nim还有一批常见的亲戚我把判定的核心结论整理成了一张速查表变体名称规则要点核心结论台阶Nim石子放在台阶上只能向下移动奇数台阶石子数的异或决定胜负威佐夫博弈两堆石子可任取一堆或两堆取同样多设差值为d较小堆为a当a等于d乘以黄金分割系数的整数部分时必败Moores Nim每次最多从k堆中取石子把每堆二进制按位相加后对(k1)取模所有位余数全为0则必败减法游戏每次只能取集合S中的数量用SG函数或找周期直接解决每次碰到带Nim字样的新题我第一件事永远是问自己四个问题这是不是公平组合游戏能不能拆成独立子游戏每一步影响几个维度能不能映射到异或或者SG回答完这四个问题大部分变体都不会再觉得陌生。这套自查流程比背任何结论都管用。5. 常见问题与排错实录5.1 三个高频WA原因这里必须聊聊我实操中踩过的坑每一条都是用罚时换回来的。第一个坑把普通Nim的异或判定直接套到反Nim上。题目里只要出现拿走最后一颗石子的人输这句话就必须走全为1的特判分支否则你以为的必败态其实是必胜态。我建议做题前先把规则抄一遍明确last move win还是last move lose再开始写代码。第二个坑读入用int导致爆精度。数据范围写着1e18你用int读不仅异或算不对连输入都可能出问题。记住一个原则博弈题的堆数可以小但每堆数量能开long long就开long long省得赛后看数据怀疑人生。第三个坑SG函数的mex数组和状态数组开小了。有些题的局面上限是1e5甚至更大你图省事开个10005结果越界访问错在哪都不知道。我的习惯是先把状态范围读出来再开数组或者用vector动态初始化坚决不猜数组大小。5.2 数据范围与复杂度判断Nim判定的复杂度是O(n)n是堆数这个几乎不可能被卡。但变体就要小心了SG打表的时间复杂度是O(状态数乘以后继数)状态数稍微大一点就会超时威佐夫博弈要用浮点数或者整数近似判断注意浮点误差保险的做法是用long double计算黄金分割系数或者干脆用手写整数比较避免精度问题。Moores Nim需要按位统计复杂度是O(n乘以位数)位数按60处理也很稳。真正的复杂度炸弹通常出现在拆堆构造题里枚举b的上限如果到1e9就一定要想数学优化而不是硬枚举。博弈题很少有单纯卡常的但真的有单纯卡爆int的。5.3 暴力对拍是博弈题的救命稻草我几乎对每道博弈题都会先写一个暴力P/N表生成器用来验证结论。核心思路很简单递归判断每个状态是P还是N伪代码如下// 状态用 vectorint 表示各堆数量只在小数据下使用 bool isP(vectorint state) { if (所有堆都是0) return true; // 无路可走轮到的人输 for (每个合法走法 next_state) { if (isP(next_state)) return false; // 能一步走到P态当前就是N态 } return true; // 所有后继都是N态当前是P态 }这个暴力能对付n不超过3、每堆不超过10的小数据。把暴力结果和异或结论对比如果不一致那一定是你结论的某个前提没满足要么游戏不是公平组合游戏要么你漏了某个合法走法要么你误用了普通Nim结论处理反Nim。我在新题上从来都是先跑对拍再提交虽然多花几分钟但能省下一整晚的WA挣扎。这个习惯帮我抓出过好几次题目其实不是Nim的坑。6. 个人心得与模版的后续扩展写到这我想分享一点自己对博弈题和数学构造题关系的体会。很多人把Nim博弈模版理解成背一个异或函数这其实浪费了它真正的价值。Nim的整套逻辑——从局面分类到异或判定再到构造一步让对手进入必败态——本身就是数学建模的最佳范例先抽象出状态再找到不变量或判据最后用一个小而美的结论解决大规模问题。我在做数学建模类的题目时也经常用这套思路凡是涉及轮流决策公平规则胜负判定的模型第一反应都是能不能化归成某个博弈结论而不是盲目写搜索。这种从模拟过程转向寻找判据的思维转换比记住任何一个模版都值钱。模版的后续扩展方向我个人觉得有三个一是把SG函数封装成能适应多种状态表示的版本配合记忆化搜索处理图上博弈二是把Nim的构造技巧迁移到方案计数方案构造类题目这类题在竞赛里越来越多三是学会用打表找规律很多变体博弈的结论都不是一眼看出来的先写暴力程序跑出小数据的P/N分布再总结规律往往比干想快十倍。我自己最近几年写博弈题基本就是这三板斧轮着上。最后再分享一个小技巧遇到不熟悉的博弈题先别急着套Nim结论。把局面写出来手动推几个小规模状态找出P态的分布规律再用异或或SG去验证。我靠这个习惯已经救回了很多道看起来完全不像Nim的题。博弈模版的意义从来不是让你背答案而是给你一套足够可靠的思考框架碰到新规则时能自己把它构造成熟悉的数学模型。这才是Nim博弈留给我们的真正财富。