1. 从一道题说起为什么“移棋子游戏”需要SG函数如果你在刷算法题时看到“1319 移棋子游戏”这个标题可能会觉得它像一道普通的博弈题。但当你点进去发现它被贴上了“sg函数模板”的标签时心里多半会“咯噔”一下。博弈论、SG函数这些词听起来就有点“劝退”。别急我最初接触时也一头雾水感觉像在看天书。但后来在实战中反复踩坑、调试、理解后我发现这其实是一个极其精巧的“解题模板”一旦掌握就能解决一大类看似复杂的博弈问题。简单来说这个游戏是这样的有一堆或多堆棋子你和对手轮流移动棋子每次移动必须遵循特定的规则比如移动到某个指定的后继位置无法移动者判负。我们的目标是判断在给定初始状态下先手是否必胜。这听起来是不是很像小时候玩的“抢30”或者“取石子”游戏没错它们本质上是同一类问题。而SG函数就是解决这类“公平组合游戏”的瑞士军刀。我之所以花时间深究这个模板是因为它在很多在线编程竞赛和面试中都是高频考点。更重要的是它代表的是一种将复杂博弈“数学化”、“公式化”的思维方式。你不需要去模拟所有可能对局只需要计算一个值就能预判胜负。这种从“模拟”到“计算”的思维跃迁才是学习SG函数的真正价值。接下来我就结合这道“1319 移棋子游戏”把SG函数从为什么需要、到怎么计算、再到如何套用模板彻底讲清楚。2. SG函数的核心将游戏状态映射为一个“必胜值”要理解SG函数我们得先忘掉那些复杂的数学定义。你可以把它想象成给游戏中的每一个可能状态局面打一个“战斗力分数”。这个分数有一个神奇的特性如果当前状态的分数是0那么轮到谁走谁就“必败”如果分数不是0那么轮到谁走谁就“必胜”并且存在一种走法可以走向“必败态”即分数为0的状态送给对手。2.1 从最简单的情况开始单堆游戏与Mex运算我们从一个最简单的“取石子”游戏开始有一堆石子数量为n。每次可以取走1颗、2颗或3颗无法取者输。这个游戏的SG函数怎么算我们定义SG(x)为当石子数量为x时这个局面的SG值。首先确定终点当x0时无石子可取当前玩家行动他立刻输掉。所以SG(0) 0必败态。对于x1玩家可以取走1颗到达x0的状态。因为可以到达SG(0)0这个必败态所以当前玩家是必胜的SG(1)应该是一个非0值。这个值是多少呢这里就引入了MexMinimum Excludant运算。Mex运算的定义是对于一个非负整数集合Mex是该集合中未出现的最小非负整数。Mex({0, 1, 3}) 2Mex({1, 2, 4}) 0Mex({}) 0SG函数的递推公式就是SG(当前状态) Mex( {所有后继状态的SG值} )。所以对于x1后继状态取1颗到达x0。后继状态SG值集合{SG(0)} {0}SG(1) Mex({0}) 1对于x2后继状态取1颗到x1取2颗到x0。后继状态SG值集合{SG(1),SG(0)} {1, 0}SG(2) Mex({0, 1}) 2对于x3后继状态取1到x2取2到x1取3到x0。后继状态SG值集合{SG(2),SG(1),SG(0)} {2, 1, 0}SG(3) Mex({0, 1, 2}) 3对于x4后继状态取1到x3取2到x2取3到x1。后继状态SG值集合{SG(3),SG(2),SG(1)} {3, 2, 1}SG(4) Mex({1, 2, 3}) 0看SG(4)0意味着当石子为4颗时先手必败。你可以验证一下先手取1后手取3先手取2后手取2先手取3后手取1。无论先手怎么取后手都能把最后1颗拿走让先手面对无石子的局面。2.2 SG函数的组合多堆游戏的胜负判定Nim和单堆游戏太简单了。实际问题往往是多堆的比如“1319 移棋子游戏”可能有多个棋子在不同的位置上。这就是组合游戏。对于多个相互独立的子游戏比如多堆互不影响的石子或多个独立移动的棋子整个游戏的SG值等于各个子游戏SG值的异或和Nim和。公式总SG SG(子游戏1) ^ SG(子游戏2) ^ ... ^ SG(子游戏n)这里的^是按位异或操作。判断胜负的定理Sprague-Grundy定理非常简洁如果总SG 0那么当前局面是先手必败态P-position。如果总SG ! 0那么当前局面是先手必胜态N-position。这简直是魔法我们不需要分析复杂的交互只需要分别计算每个独立棋子或石子堆所在状态的SG值然后全部异或起来看结果是否为0即可。注意这里有一个极其关键的实操点也是我早期最容易混淆的地方。“子游戏”的划分必须基于“独立性”。在“移棋子游戏”中通常每个棋子的移动是独立的一个棋子的移动不影响其他棋子的状态和可移动选项所以每个棋子可以看作一个子游戏。但如果规则是“移动一个棋子后会改变棋盘格局从而影响其他棋子的可移动性”那它们就不是独立子游戏不能简单用异或和。好在“1319”这类模板题通常都假设独立性。3. “1319 移棋子游戏”的解题框架拆解现在我们把这个理论框架套到具体的题目上。虽然原题描述可能因平台而异但“移棋子游戏sg函数模板”这个模式是固定的。我们假设一个典型描述有一个有向无环图DAG图上有若干个棋子位于不同的节点上。玩家轮流任选一个棋子将其沿有向边移动到下一个节点。无法移动即棋子位于出度为0的节点的玩家输。3.1 问题建模与状态定义第一步永远是建模。我们需要把游戏规则映射到SG函数模型里。游戏状态由所有棋子的位置共同决定。但由于独立性我们可以拆解。子游戏每个棋子的移动是一个独立的子游戏。子游戏状态单个棋子所在的图节点编号就是该子游戏的状态。状态转移如果从节点u有一条有向边到节点v那么状态u可以转移到状态v。这对应了“将棋子从u移动到v”的操作。终态无法操作的状态出度为0的节点。当棋子在这里时当前玩家无法移动它这个子游戏对他而言就结束了。根据定义终态的SG值为0。所以我们的任务很清晰给定一个有向图DAG和k个棋子的初始位置pos[i]。预处理计算出图中每个节点的SG值。对于每个棋子查找其初始位置节点的SG值记为sg_i。计算total_sg sg_1 ^ sg_2 ^ ... ^ sg_k。如果total_sg ! 0输出”先手必胜”通常用”win”或”first”表示否则输出”后手必胜”。3.2 计算单个节点的SG值记忆化搜索DFS如何计算每个节点的SG值根据公式SG(u) Mex( { SG(v) | 存在边 u-v } )。由于图是DAG无环我们可以用记忆化搜索DFS来自顶向下或自底向上计算。我强烈推荐使用DFS记忆化因为它的思路最直观代码也容易写对。伪代码如下from functools import lru_cache # 假设 graph[u] 存储节点u的所有后继节点v的列表 graph [...] # 邻接表 lru_cache(maxsizeNone) def get_sg(u): 计算节点u的SG值 if not graph[u]: # 如果u没有后继节点出度为0是终态 return 0 # 收集所有后继节点的SG值 successor_sg_set set() for v in graph[u]: successor_sg_set.add(get_sg(v)) # 计算Mex mex 0 while mex in successor_sg_set: mex 1 return mex这里有几个实操心得和避坑点一定要用记忆化同一个节点的SG值只需要计算一次。不用记忆化的话复杂度会指数爆炸。终态判断要准确终态出度为0的SG值一定是0。这是递归的基准情况。Mex的计算效率上面用while循环找mex的方法在SG值范围不大时是OK的。如果后继很多可以稍微优化比如用一个布尔数组标记但通常题目中SG值的范围不会超过节点数所以简单循环足矣。DAG的保证题目通常会保证是有向无环图。如果有环游戏可能无法结束SG函数会陷入无限递归。如果题目没说你需要确认规则是否可能导致循环局面。对于“移棋子游戏”模板通常都是DAG。4. 模板代码实现与细节剖析理解了原理我们来看完整的代码模板。我会用Python实现并逐行解释关键细节。import sys sys.setrecursionlimit(1000000) # 防止递归深度过大 from functools import lru_cache def solve(): # --- 1. 读入数据 --- n, m map(int, sys.stdin.readline().split()) # n个节点m条边 graph [[] for _ in range(n1)] # 节点编号从1开始多开一个位置方便 for _ in range(m): u, v map(int, sys.stdin.readline().split()) graph[u].append(v) # 构建有向图 k int(sys.stdin.readline()) # 棋子数量 positions list(map(int, sys.stdin.readline().split())) # 每个棋子的初始位置 # --- 2. 记忆化搜索计算每个节点的SG值 --- lru_cache(maxsizeNone) def sg(u): # 如果节点u没有出边是终态SG0 if not graph[u]: return 0 # 收集所有后继状态的SG值 s set() for v in graph[u]: s.add(sg(v)) # 计算mex mex 0 while mex in s: mex 1 return mex # --- 3. 计算总异或和 --- total_xor 0 for pos in positions: total_xor ^ sg(pos) # --- 4. 输出结果 --- # 根据Sprague-Grundy定理 if total_xor ! 0: print(win) # 或 first, 先手必胜 等根据题目要求 else: print(lose) # 或 second, 后手必胜4.1 代码中的关键细节与选择递归深度sys.setrecursionlimit在Python中非常重要。对于大的DAG比如上万个节点递归深度可能超过Python默认限制通常是1000导致RecursionError。直接设一个大的值如1e6是安全的做法。节点编号很多题目节点从1开始编号。我们初始化graph时开n1个槽位graph[0]空着不用这样下标和题目输入直接对应减少出错的概率。lru_cache装饰器这是Python实现记忆化最优雅的方式。maxsizeNone表示缓存不限大小。它自动存储了sg(u)的返回值下次遇到相同的u直接返回是线性时间复杂度的保证。异或运算Python中的^是按位异或。total_xor ^ sg(pos)等价于total_xor total_xor ^ sg(pos)。初始值0异或任何数等于那个数本身。胜负判断total_xor ! 0则先手必胜。这是定理直接套用不需要怀疑。4.2 一个完整的模拟案例假设我们有一个简单的图4个节点边为 1-2, 1-3, 2-4, 3-4。节点4是终态SG0。计算SG(2)后继只有4集合{0}mex1。计算SG(3)后继只有4集合{0}mex1。计算SG(1)后继有2和3集合{SG(2), SG(3)} {1, 1} {1}mex0。现在有两个棋子初始位置分别在节点1和节点2。sg(1) 0sg(2) 1total_xor 0 ^ 1 1 ! 0所以先手必胜。先手如何赢先手需要移动一个棋子使得移动后的总SG值变为0把必败态送给对手。当前总SG1二进制01。看棋子1在节点1SG0从节点1可以走到节点2SG1或节点3SG1。如果走这个棋子新的总SG (总SG ^ 旧sg值 ^ 新sg值) (1 ^ 0 ^ 1) 0。可行先手把棋子1从节点1移动到节点2或3总SG变为0后手面对必败态。验证棋子2在节点2SG1从节点2只能走到节点4SG0。如果走这个棋子新的总SG (1 ^ 1 ^ 0) 0。也可行先手把棋子2从节点2移动到节点4同样能制造必败态给后手。所以先手有至少两种必胜走法。这个模拟展示了如何从SG值反推具体策略。5. 常见变种与思路扩展掌握了模板我们就能举一反三。很多博弈题都是这个模板的“变装”。5.1 变种一移动规则不是DAG而是有环图标准的SG函数要求游戏必须在有限步内结束所以状态图必须是DAG无环。如果图中有环就可能出现无限循环。这时通常需要特殊处理判断平局或循环题目目标可能变为判断是否“先手必胜”或“可能平局”。这需要更复杂的分析可能用到拓扑排序结合必胜/必败态传播或者搜索带状态标记状态节点轮到谁走。这超出了基础SG函数范围但知道这个边界很重要。5.2 变种二每次移动的不是棋子而是对一堆石子进行操作Nim游戏系列经典Nim游戏有n堆石子每次任选一堆取走任意正数颗至少1颗最多整堆。这其实是“移棋子游戏”的一个特例你可以把每一堆石子想象成一个子游戏。对于一堆数量为x的石子它的状态就是x。它的后继状态是0, 1, 2, ..., x-1因为可以取走任意颗剩下0到x-1颗。可以证明SG(x) x。因此总SG值就是所有堆石子数的异或和。这就是著名的Nim定理。所以Nim游戏是SG函数的一个直接结论。5.3 变种三每次操作必须移动到“特定”的后继集合有向图移动这就是我们的“1319”模板本身。它比Nim更通用因为后继状态不一定是连续的数值而是由有向边任意定义的。这要求我们必须通过DFS或拓扑排序来计算每个节点的SG值。5.4 变种四每次操作可以移动多个棋子如果规则允许一次移动多个棋子比如“每次可以选择1到m个棋子每个棋子移动一步”这破坏了子游戏的独立性吗不一定。关键在于移动是否同时影响多个子游戏的状态。如果只是允许你从多个独立的子游戏中各操作一步那么整个游戏的SG值仍然是每个子游戏SG值的异或和。因为你的一次“复合操作”等价于在多个独立游戏上各走一步这在SG定理中仍然是允许的。但如果操作是“移动A棋子会导致B棋子消失”那就不独立了。6. 实战调试与性能优化要点理论懂了代码写了一提交可能还是错。这里分享几个我调试这类题目时踩过的坑和优化技巧。6.1 为什么总是WA错误答案——排查清单图建错了吗这是最最常见的错误。检查输入是有向边还是无向边题目通常是有向的。检查节点编号是否从1开始你的graph数组下标是否匹配递归基错了吗终态无法操作的状态的SG值一定是0。在你的题目中什么是终态是出度为0的节点吗确认你的if not graph[u]: return 0这行代码逻辑是否正确。记忆化生效了吗确保你的sg函数被lru_cache装饰或者用了一个全局的dp数组来存储计算结果。可以在函数开头加一句打印看看同一个u是否被重复计算多次。异或和计算错了吗确保你是对每个棋子的初始位置的SG值求异或而不是对位置编号本身求异或。total_xor ^ sg(pos)不是total_xor ^ pos。多组数据清空了吗如果题目有多组测试数据必须在每组开始前清空graph、重置记忆化缓存sg.cache_clear()如果用了lru_cache或者重新初始化dp数组。6.2 性能优化当图很大时怎么办上述DFS记忆化搜索的时间复杂度是O(NM)其中N是节点数M是边数。对于每个节点和每条边只访问一次这已经是理论最优了。但在极端情况下比如N10^5递归的常数开销和缓存查找可能成为瓶颈。迭代法拓扑排序既然图是DAG我们可以用拓扑排序从后往前从出度为0的节点开始递推计算SG值。这避免了递归开销有时更快。from collections import deque indegree [0] * (n1) # ... 建图时同时计算入度 ... # 找到所有终态出度为0的节点初始化其SG值为0 sg_value [0] * (n1) # 按拓扑逆序可以使用拓扑排序后逆序遍历或者从终态反向BFS计算 # 需要反向建图r_graph[v] 存储能到达v的节点u方便从后继找前驱这种方法代码稍复杂但更稳定且没有递归深度限制。不过对于大部分竞赛题DFS记忆化完全够用。Mex计算的优化如果某个节点的出度非常大比如上万用set和while循环找mex可能稍慢。可以用一个布尔数组vis来标记后继SG值是否出现然后找第一个vis[i]False的i。因为SG值不会超过节点数所以这个数组大小设为n2就够了。6.3 一个思维陷阱SG值为0就一定输吗这是初学者最容易混淆的点。SG(u)0 表示“在当前这个子游戏单个棋子中轮到你移动时你必败”。但是整个游戏由多个子游戏组成。即使你面对一个SG0的子游戏如果其他子游戏的SG值异或和非0你仍然可以通过操作其他子游戏来赢得整个比赛。胜负只取决于总异或和。所以不要孤立地看单个棋子的SG值一定要看全局的异或结果。7. 从模板到精通理解SG函数的本质最后我想分享一下超越这道题本身的思考。SG函数不仅仅是一个解题模板它背后是博弈状态的数学抽象。你可以把每个游戏的局面看作一个点合法操作看作有向边这样就形成了一个博弈状态图。SG函数给每个状态赋予一个非负整数值这个值神奇地编码了该状态的“胜负势能”。Mex运算保证了“必败态”的SG值为0并且从任何“必胜态”SG0都可以通过一步操作到达某个“必败态”SG0。而异或运算Nim和则完美刻画了多个独立游戏组合后的胜负规律。这种抽象的力量在于它把千变万化的游戏规则统一到了一个计算框架下。无论规则是取石子、移棋子、翻硬币还是其他只要你能定义出清晰的状态。列出从一个状态能到达的所有后继状态。识别出无法操作的状态终态。 你就能套用SG函数模型通过计算来判断胜负。所以当你再看到“sg函数模板”时不要把它当成一个黑盒。理解其每一步背后的“为什么”为什么用Mex为什么用异或为什么终态SG0想通了这些你就能自己推导出模板并且有能力去解决那些看起来不像模板的博弈问题。这才是刷这道“1319 移棋子游戏”的最大收获——获得一种分析和解决一大类问题的通用思维工具。