Nim博弈几乎是所有算法竞赛选手绕不开的第一道坎。我当年第一次碰它是在一场练习赛的签到题里题目描述简单到不能再简单几堆石子两个人轮流从任意一堆里取出任意正整数个石子取走最后一颗的人获胜问先手能否必胜。当时我没接触过博弈论二话不说写了个深度优先搜索直接对着状态枚举结果样例过了提交就超时。后来才知道这题的背后就是Nim博弈而且它有一个漂亮到近乎作弊的解法不用搜索不用动态规划把所有堆的石子数全部按位异或起来看结果是不是0胜负立刻见分晓。这篇东西我想把Nim博弈的模版思路完整拆给你看重点放在三件事一是数学上为什么异或和能决定胜负二是必胜局面下怎么构造出那一步关键操作三是常见的Nim变体、模板代码以及我踩过的坑。适合刚开始学博弈论的新手也适合已经会判胜负但还不会写构造方案、想系统整理博弈模板的选手。1. 先搞清楚Nim博弈到底在玩什么1.1 一个看似简单却充满套路的游戏规则Nim博弈的标准规则是这样的桌面上有若干堆石子每堆石子的数量可以互不相同。两个玩家轮流行动每次行动必须从某一堆中取走至少一颗石子取走的数量不能超过该堆剩余总数。谁取走整个棋盘上最后一颗石子谁就获胜。注意这里的“获胜”指的是正常规则也就是你取完最后一颗石子时游戏立刻结束对方没有下一步。这个规则里有几个容易忽略的细节。第一每次只能在一堆里取不能同时动多堆第二同一轮里取的数量没有上限整堆端走也可以第三石子的堆数和每堆的数量在开局之后都是公开信息不存在任何隐藏信息。因此Nim博弈属于典型的“公平组合游戏”两个玩家面对的信息完全对称每一步都是完全确定的。很多题目会拿其他东西来包装比如棋子、纸牌、巧克力块但本质上只要满足“每轮只能在一个独立集合里减少数量减少量由自己决定”这个结构就可以抽象成Nim博弈。看穿包装识别出数学模型比记住结论更重要。1.2 胜负判定的数学结论为什么是异或而不是求和Nim博弈的胜负判定有一个非常简洁的结论设每堆石子数为 (a_1, a_2, ..., a_n)计算它们的异或和 (S a_1 \oplus a_2 \oplus ... \oplus a_n)。如果 (S 0)当前局面是必败态如果 (S \neq 0)当前局面是必胜态。第一次看到这个结论的人十有八九会一脸茫然为什么偏偏是异或而不是求和、求乘积或者别的什么运算我最初也背过这个结论但做题时一遇到变体就翻车原因就在于没吃透里面的数学结构。试着把所有石子数写成二进制然后逐位去看。拿一个具体例子三堆石子数量分别是1、2、3。二进制是01、10、11。把所有数对齐01 10 11从低位到高位逐位统计1的个数最低位有2个1是偶数最高位有2个1也是偶数。异或运算的本质就是“按位做不进位的加法”或者说按位奇偶校验某一位上1的个数是奇数异或结果这一位就是1是偶数这一位就是0。所以 (1 \oplus 2 \oplus 3 0)这个局面是必败态。如果你改用求和1236完全看不出0的特征方向直接就走偏了。异或之所以能成立是因为它精确刻画了“每一堆二进制位上1的数量的奇偶性”而这刚好对应了公平组合游戏里“每种规模的状态是否能被完全配对”的核心规律。1.3 为什么Nim博弈总爱以构造题的形态出现Nim博弈在算法题里最常见的出场方式不是直接裸题而是藏在构造题和交互题里。构造题的特征是结论本身不难难的是“你凭什么想到这一步”。Nim博弈恰好具备这样的特质判定条件极其简洁但把它包装成棋盘移动、卡片翻转、石头变色之后很多选手就认不出来了。从出题人的视角看Nim博弈也是一个很好的难度调节器。基础题可以只问“先手能不能赢”中等题会要求“输出先手第一步该拿哪个堆、拿几颗”难题则会把Nim嵌进SG函数、阶梯博弈或者带限制的取石子规则里。所以“模板”二字不只是指一段判胜负的代码更是一整套从识别模型到输出方案的思维流程。2. 模板思路先把胜负判断写对2.1 判断胜负的模板代码先给一段最基础、最常用的Nim胜负判断模板。这段代码我在赛场上直接抄过很多次区别只是输入格式偶尔会变。#include bits/stdc.h using namespace std; int main() { int n; while (cin n n) { long long x, xorsum 0; for (int i 0; i n; i) { cin x; xorsum ^ x; } cout (xorsum ? First wins : Second wins) \n; } return 0; }代码逻辑很简单每读入一个数就和当前的异或和做一次异或。全部读完后如果结果非0先手必胜如果为0先手必败。多组数据时每一轮都要把异或和重新置0这个细节看起来不值一提但我见过好几个同学因为忘了重置变量导致后面的数据全部判错。这个模板里我把石子数声明成了long long。虽然经典Nim题目里单堆石子数通常不超过int范围但很多变体题为了卡人会把数据范围放大比如单堆可以达到 (10^{18}) 量级。异或运算本身不会像加法那样溢出所以用long long更多是为了读入安全避免类型转换出问题。2.2 异或为什么能判定胜负一次二进制视角的实验如果你还觉得异或结论是凭空冒出来的我建议你亲手做一个小实验。把局面 ((1,2,3)) 的所有合法后继状态列出来你会发现无论你从哪一堆取多少颗得到的新局面异或和都不会是0换句话说从必败态出发所有走法都会通向必胜态。再看局面 ((1,2,4))它的异或和是 (1 \oplus 2 \oplus 4 7)非0这时一定存在一个走法能把局面变成异或和为0的状态。这件事背后的数学逻辑可以这样理解异或和为0的局面等价于所有二进制位上1的个数都是偶数。这时无论你改变哪一堆由于该堆在某一位上的1会变成0或0变成1至少会有一位1的数量从偶数变成奇数异或和必然从0变成非0也就是说必败态的任何一步都会把局面送给对方当必胜态。反过来异或和非0的时候一定存在一个合法的取石子操作能使新局面的异或和变成0于是主动权就回到了自己手里。接下来的第3章会专门讲这个构造过程。2.3 边界情况与常见坑位写Nim模板时有几个边界情况值得注意。我整理成了一个小表格场景正确行为容易犯的错只有一堆石子 (n1)异或和等于该堆数量非0则必胜误把“只有一堆”当成必败态某一堆数量为00不会影响异或结果正常参与运算把0当成“没有堆”改变n多组数据输入每轮重置异或和为0忘记重置后续数据全部错误石子数接近 (10^{18})用long long读入和计算用int读入导致溢出输入以0作为结束标志先读nn0退出循环把n0当成一组有效数据参与判定只有一堆石子时先手直接把整堆端走就赢了所以异或和就是这堆的数量显然非0判必胜。这个例子最简单但恰好能检验你对异或结论的理解它不是某种神秘的“总和”而是独立堆之间的一种状态耦合。3. 构造移动把必胜态一步打成必败态3.1 构造的核心原理从异或和的最高位下手判断胜负只是第1步很多题目会进一步要求你输出构造方案如果先手必胜请给出第一步的操作。这时候我们需要在异或和 (S \neq 0) 的前提下找到某一堆 (a_i)把它变成一个新的值 (b_i)使得所有堆的新异或和为0。关键在于一个不等式(b_i a_i \oplus S a_i)。为什么一定存在这样的 (i)因为 (S) 非0取 (S) 的二进制表示里最高的那一位假设它是第 (k) 位。既然这一位为1那么在若干堆石子中至少有一堆 (a_i) 的第 (k) 位也为1。我们对这一堆做异或 (S)由于 (S) 的第 (k) 位是1(a_i) 的第 (k) 位会变成0而比 (k) 更高的位上(S) 全是0所以 (a_i) 的高位不变。低位无论如何变化整个数从数值上看因为最高位从1掉成了0结果必然小于原来的数。这就保证了操作合法我们确实是在减少这一堆的数量。3.2 构造算法的模板代码把上面的原理落成代码就是一段非常实用的构造模板。竞赛里最常见的输出格式是要求给出“取走哪一堆取走多少颗”也可能要求直接输出操作后的那堆剩余数量我下面这段代码把两个信息都输出了方便改。#include bits/stdc.h using namespace std; int main() { int n; cin n; vectorlong long a(n); long long xorsum 0; for (int i 0; i n; i) { cin a[i]; xorsum ^ a[i]; } if (xorsum 0) { cout Second wins \n; return 0; } for (int i 0; i n; i) { long long nxt a[i] ^ xorsum; if (nxt a[i]) { cout Pick pile i 1 : take a[i] - nxt stones, leaving nxt \n; return 0; } } return 0; }这里有一个细节循环里找到第一个满足条件的位置就停止因为题目通常只需要输出任意一种合法方案。有些题会要求优先输出编号最小的堆那从0号开始遍历就天然满足如果要求字典序最大就倒着遍历。这个排序逻辑根据题目调整即可。3.3 构造方案的数学验证为什么用 (a_i \oplus S) 替换掉 (a_i) 之后整个局面的异或和一定是0这个证明很优雅推导过程只有三步记原异或和为 (S)我们只修改第 (i) 堆从 (a_i) 变成 (a_i \oplus S)其他堆不变。那么新局面的异或和为[ S S \oplus a_i \oplus (a_i \oplus S) ]异或满足交换律和结合律右边可以重新排列成[ S S \oplus S \oplus a_i \oplus a_i 0 ]因为 (x \oplus x 0)整个式子归零。这就是构造方案永远安全的原因我们选择的恰好是把“总异或和”加到某一堆上而这一堆又因为它本身和 (S) 的位关系必然变小所以它是一步完全合法的操作。拿具体数据走一遍。假设局面是 ((5, 7, 8))计算异或和(5 \oplus 7 2)(2 \oplus 8 10)所以 (S 10)二进制是1010。从第0堆开始尝试第0堆(5 \oplus 10 15)15 5不合法。第1堆(7 \oplus 10 13)13 7不合法。第2堆(8 \oplus 10 2)2 8合法。因此先手应该把第3堆从8颗取到2颗也就是拿走6颗。验证新局面的异或和(5 \oplus 7 \oplus 2 0)必败态转移给对方先手进入必胜轨道。4. 常见变体与模板扩展4.1 反Nim博弈最后取到石子的人反而输经典Nim有一个非常经典的变体叫反Nim规则改成“取走最后一颗石子的人输”。这个改动看似很小结论却完全不同不能直接套异或判定了。反Nim的判定可以这样记如果所有堆的石子数都为1那么堆数为偶数时先手必胜堆数为奇数时先手必败如果存在某一堆石子数大于1那么异或和非0时先手必胜异或和为0时先手必败。写成代码大概是bool AntiNimWin(vectorlong long a) { long long xorsum 0; bool allOne true; for (long long v : a) { if (v 1) allOne false; xorsum ^ v; } if (allOne) { return (a.size() % 2 0); } return xorsum ! 0; }为什么会多出“全为1”的特判因为当所有堆都只有1颗时游戏变成“每个人必须取1颗谁取最后1颗谁输”先手能做的只是决定游戏轮数的奇偶性。当有一堆以上大于1时局面又回到了经典Nim的“可转化”结构只是最后一步的输赢归属发生了偏移所以异或和判断仍然有效。4.2 带取子上限的Nim每堆变成巴什博弈有些题目会加一条限制比如每次从一堆里至多取k颗其他规则不变。这时候不能直接对原石子数做异或因为每次能取的量被卡住了上限。对于单独的每一堆这是一个巴什博弈如果一堆有 (m) 颗每轮只能取1到k颗那么当 (m \bmod (k1) 0) 时这堆是必败态否则是必胜态。多堆组合之后正确的做法是先把每堆的石子数转化为 (m \bmod (k1))再用这组“余数”做异或判断。这个过程背后的道理是每堆内部都存在一个周期性的等价状态长度是 (k1)。无论是先手还是后手当一局里的某一堆被取到某个余数时对方总能通过补齐差值把局面拉回自己控制的节奏。把这个周期理解成“每堆真正的博弈值”Nim模板就又能用了。这类变体是最常见的中档博弈题套路先识别单个组件的等价状态再用Nim异或组合它们。本质上就是SG函数思想的雏形。4.3 阶梯Nim与SG函数泛化模板阶梯Nim是另一个经典扩展若干堆石子排成一排每次只能把某堆的若干颗石子向左移动一堆移到第0格或者最左端。表面上看和取石子完全不同但它有一个著名的结论只考虑位置编号为奇数的堆做Nim异或偶数堆可以忽略。这个结论的直观解释是把石子从奇数位置移到偶数位置相当于把“可控资源”从奇数位移走而对方如果从偶数位移回奇数位你可以立刻再移走保持奇数位的异或优势不变。所以只有奇数位堆的数量决定胜负。如果题目更复杂没法一眼看出等价状态就要用SG函数做泛化。对每个独立状态算一个SG值多状态组合的胜负等于所有SG值的异或和。一个常用的记忆化搜索模板如下vectorint gao(vectorint grundy, int n) { if (grundy[n] ! -1) return grundy[n]; bool vis[128] {false}; for (int i 1; i n; i) vis[gao(grundy, n - i)] true; int g 0; while (vis[g]) g; return grundy[n] g; }用SG函数时最容易犯的错是“乱打表”不理解状态的定义直接暴力枚举后继最后打出来的表自己都不知道代表什么。正确的做法是先把每个状态的后继集想清楚再求mex。这跟Nim模板的数学推导是一个思路状态要精确刻画而不是凭感觉。5. 实战避坑与问题排查5.1 最容易踩的四个坑我见过太多Nim博弈提交记录在WA和RE之间反复横跳自己也踩过不少。排在最前面的坑永远是“异或写成加法”这几乎成了博弈题新手村的标志性错误。异或和0并不代表加和0就拿(1,2,3)来说加和是6异或是0用加法判的话必败态会被判成必胜态。第二个坑是反Nim忘记特判“全为1”的情况。很多人背了异或判定就直接用结果遇到几个堆全是1的数据输出正好反了。这里给个记忆抓手异或判定只适用于经典Nim反Nim必须先看有没有堆大于1。第三个坑是构造方案时选了 (a_i \oplus S a_i) 的堆。如果你的代码没有判断变小就直接输出计算机会认为你先手把石头变多了这显然非法。所以构造时必须有if (nxt a[i])这个条件。第四个坑出现在多组数据输入上。很多在线题目以0作为结束标志也有的提前说明了组数T。我犯过的错误是忘记把异或和重置导致第二组数据的判定被第一组残留值污染。每次循环开头重新声明变量或者显式置0是最保险的写法。症状可能原因检查方法判胜负结果正好反了用了加和代替异或用(1,2,3)手动算witness反Nim题过不了没处理全1特判构造全1数据自测输出构造步骤非合法没检查变小条件把输出还原后求异或和多组数据全部混乱异或和变量未置0检查循环作用域5.2 题目包装识别三步还原Nim模型很多Nim题不会直白地说“有几堆石子”而是会用其他道具来包装。我有一个固定的三步还原法几乎可以应对大多数伪装题。第一步找“轮流操作”和“操作不影响他人选择”。博弈题的核心就是双方交替行动行动只改变当前局面的某个局部。第二步把这个局部抽象成“堆”。比如棋盘上有几叠棋子每叠可以向前移动若干格那么一叠棋子就是一堆石子能移动的格数就是石子的数量。第三步检验每次操作的独立性。如果每轮只能操作一个局部且操作的结果等价于减少该局部的“资源量”那就可以套Nim模板。举一个例子题目给出n个棋子放在一维数轴上每次可以把某个棋子向正方向移动若干格不能越过对方。这个模型还原之后实际上是把相邻棋子之间的空隙看作一堆石子移动棋子就等价于从这堆石子里取走若干颗。只要完成这个映射异或判断立刻能用。5.3 小规模暴力对拍验证法模板写完之后最稳的验证方式不是直接提交而是写一个爆搜代码对拍。对于小规模数据深度优先搜索可以直接枚举所有状态bool dfs(vectorint a) { int xorsum 0; for (int v : a) xorsum ^ v; if (xorsum 0) return false; // 当前是必败态 for (int i 0; i a.size(); i) { for (int take 1; take a[i]; take) { vectorint b a; b[i] - take; if (!dfs(b)) return true; // 存在一步走向必败态 } } return true; }把这段爆搜和你的Nim模板放在一起随机生成几千组小数据只要有一组不一致就说明模板有问题。这个对拍思路不只适用于Nim写任何博弈类题目都可以这么干。比赛时间充裕的时候我会先写爆搜确认理解题意再用数学模板去交题双保险能省下大量罚时。6. 从Nim模板到更广的数学思维6.1 建模类博弈问题怎么借力Nim博弈不仅仅是一道算法题它也是很多数学建模问题里博弈模型的基石。无论是竞争决策、资源调度还是策略选择只要问题满足“双方轮流行动、完整信息、零和结局”都可以尝试用公平组合游戏的框架去描述。这时Nim模板中的异或思想、状态划分和必败态构造就成了搭建数学模型的参考工具。数学建模里常见的一个误区是遇到博弈就直接上复杂的混合策略或者纳什均衡。实际上如果问题里的决策结构是离散的、确定的并且没有随机因素那么公平组合游戏的胜负判定模型会更有效。Nim教会我们的不只是那一个异或结论而是“把复杂状态拆成独立组件再逐位或逐项合并”的建模思维。6.2 异或按位思维在构造题中的复用Nim博弈里的“异或”不是只在这一个模型里有用。很多构造题都会用到按位运算的性质尤其是“找最高位”“在某一位上配对”“用异或消除成对状态”这些手法。比如有一类题目要求把一个数组分成若干组让每组内的异或和满足某种条件思路就来自Nim里的“每一位独立考虑”。再比如某些交互题要求你根据对方的操作反推出策略本质上也是在维护一个按位异或的状态池。二进制位的独立性和奇偶性本身就是构造题里非常趁手的工具。6.3 建立自己的博弈论模板库从Nim开始我建议每个人都搭建一个自己的博弈论模板库不用花哨但要包含四样东西判定代码、构造代码、证明摘要、对拍脚本。特别是证明摘要哪怕只是三五行也能帮你回忆起“为什么是异或而不是加法”。模板库里的代码不要直接复制粘贴到比赛里最好的做法是自己从头敲一遍把每一步注释都写清楚。我自己的博弈模板至今还留着早年写的“异或和0是必败态”备注以及一堆稀奇古怪的变体特判记录。这些东西在关键时刻比任何现成模板都好用因为它们已经变成了你自己的思维路径。7. 实操心得把Nim模板真正变成自己的东西7.1 我当年是怎么把异或结论想通的Nim结论我第一次接触时完全靠背但每次做题心里都不踏实。真正想通是在某天我把一堆石子数量写成二进制列成一竖排之后。当时盯着那些0和1看了很久突然意识到异或的每一位其实是在统计“这一位上1的个数是奇数还是偶数”。必败态之所以必败是因为无论你动哪一堆都至少会翻转一个二进制位上的奇偶性而对方总有办法再把所有奇偶性恢复成偶数。这个认知一旦建立后面的构造题就全都通了。所以如果你现在还在硬背结论我强烈建议你拿纸笔把二进制位数对齐亲自列几组局面观察。7.2 两条分开记的判断口诀我后来把Nim知识压缩成两句话做题时分开调用很少再出错。第一句是“判胜负看异或和为0则先手输”。第二句是“构造走法找最高位异或后变小才合法”。这两句话一个是给裁判用的一个是给先手用的场景完全不同。很多新手把两个步骤混在一起拿到非0异或和就开始一顿操作结果忘了判断选择哪一堆导致输出的走法不合法。这两条口诀分开记逻辑就清晰了。7.3 一个我自己一直在用的小习惯最后分享一个小习惯每次写完Nim模板相关代码我都会手动构造一个“边界数据”和一个小规模随机数据。边界数据包括只有一堆、两堆数量相等、所有堆都是1的情况随机数据用对拍确认。这套流程看起来很笨但成了我比赛里的肌肉记忆也帮我避免了很多次因为一个小细节而整题爆掉的悲剧。Nim博弈的数学结论可以背但思维上的透彻才真的属于你。