这还是 SG 吗？

· · 算法·理论

本文经 ChatGPT 的略微学术润色。
如果有问题记得在评论区踹我一脚。

背景

事情是这样的，这是百度之星 2026 第一场初赛的第六题：
场上的我：这应该……是道简单题吧。
于是对着它疯狂思考约 1h，然后弃掉了。
第二题代码能力问题没写出来，然后就倒闭了。
后面回来思考这题，然后 10min 就会了。
大失败。
后面发现这其实和无穷序数有着很大的关联，那就借这道题瞎说点东西吧。
因为这里介绍的 SG 超出了正常的 SG 范围，所以如果不会标准 SG 出门左转。

题解

SG 值分析

定义 \operatorname{SG}(a,b,c) 为当题目中的一个游戏机状态为 (a,b,c) 时，这个状态的 SG 值。
定义 \operatorname{MEX}(A) 为集合 A 的 \operatorname{MEX}，其定义为“最小的不属于 A 的非负整数”。

接下来考虑 $\operatorname{SG}(a,b,1)$。 先从 $b=0$ 入手。当 $a=0$ 时，此时你只能进行第二种操作，那么可以转移到 $(x,x,0)(x\ge b)$，对应 SG 值为 $x$（注意，这里的 $x$ 没有上界）。 因为我们固定了 $b=0$，那么子状态的集合为 $\{0,1,2,\cdots\}$，如果这时候的 SG 值仍为非负整数，那么永远可以从这个集合里找到一个 SG 值等于它的子状态，和 SG 值的定义不符。 这说明 SG 值已经无法限制在非负整数中，同时子状态集合的 $\operatorname{MEX}$ 就根本不存在了。 那咋办？我们发明一个新的记号 $\omega$，把它排在所有非负整数的后面，具体地，大小关系为 $$0<1<2<\cdots<\omega$$ 那 $\operatorname{SG}(0,0,1)$ 就很明显为 $\omega$ 了。 接下来我们再考虑 $a=1$。 同理得进行第二种操作所得到的子状态集合为 $\{0,1,2,\cdots\}$，但因为我们还可以进行第一种操作到达 $(0,0,1)$，所以子状态集合还要再添加一个 $\omega$。 此时 $\omega$ 也用不了了，那咋办？ 那我们就继续构造，再 $\omega$ 的后面再排上一个 $\omega+1$，此时 SG 值就成了 $\omega+1$。 那么我们再在 $\omega+1$ 之后排上一个 $\omega+2$，就可以得到 $\operatorname{SG}(2,0,1)=\omega+2$。 以此类推得到 $\operatorname{SG}(a,0,1)=\omega+a$。 自然地，$\operatorname{MEX}$ 的定义也需要随之扩展。我们仍然把 $\operatorname{MEX}(A)$ 理解为“不属于 $A$ 的最小值”，只不过它的取值范围不再局限于非负整数，而是也包含我们刚刚构造出的这些新对象。例如，$\operatorname{MEX}(\varnothing)=0$，而 $\operatorname{MEX}(\{0,1,2,\cdots\})=\omega$。 --- 接下来我们考虑 $b>0$。 当 $a=0$ 时，$\operatorname{SG}(0,b,1)=\operatorname{MEX}(\{ b,b+1,\cdots\})=0$。 我们假定 $a<b$，那么 $a=1$ 时，$\operatorname{SG}(1,b,1)=\operatorname{MEX}(\{0, b,b+1,\cdots\})=1$，同理 $\operatorname{SG}(2,b,1)=\operatorname{MEX}(\{0,1,b,b+1,\cdots\})=2$，$\operatorname{SG}(a,b,1)=\operatorname{MEX}(\{0,1,\cdots,a-1,b,b+1,\cdots\})=a$。 这个规律会在 $a=b$ 的时候被打破，此时两个子状态的连续段就连成了一段，$\operatorname{SG}(b,b,1)=\operatorname{MEX}(\{0,1,\cdots,b-1,b,b+1,\cdots\})=\omega$。 那么容易得到 $\operatorname{SG}(b+1,b,1)=\operatorname{MEX}(\{0,1,\cdots,b-1,b,b+1,\cdots\} \cup \{\omega\})=\omega+1$。 以此类推，得 $\operatorname{SG}(b+x,b,1)=\operatorname{MEX}(\{0,1,\cdots,b-1,b,b+1,\cdots\}\cup \{\omega,\omega+1,\cdots,\omega+x-1\})=\omega+x$。 综合上述的所有情况（包括 $b=0$），可得 $\operatorname{SG}(a,b,1)=\begin{cases}a&a<b\\\omega+a-b&a\ge b\end{cases}$。 --- 接下来考虑 $c=2$，先从 $a=0$ 入手。 此时你可以通过第二种或第三种操作转移到所有 $(x,x,1)(x\ge b)$ 和 $(x,x,0)$，但 $(x,x,1)$ 的 SG 值都是 $\omega$，故子状态的 SG 值集合为 $\{0,1,2,\cdots\} \cup \{\omega\}$，取 $\operatorname{MEX}$ 后得到 SG 值为 $\omega+1$。同时也可以得到此时的 SG 值与 $b$ 无关。 $a=1$ 时除了上述状态也可以转移到 $(0,b,2)$，SG 值为 $\omega+1$，故此状态的 SG 值为 $\omega+2$。 以此类推得到 $\operatorname{SG}(a,b,2)=\omega+a+1$。 --- 接着考虑 $c=3$，同样从 $a=0$ 入手。 此时你可以通过第三种操作到达所有的 $(x,x,0)$ 和 $(x,x,1)$，所以 SG 值至少为 $\omega+1$。 而第二种操作可以到达所有 $(x,x,2)(x\ge b)$，对应值为 $\omega+x+1$。 所以当 $a=0<b$ 时，其子状态集合为 $\{0,1,2,\cdots\} \cup \{\omega,\omega+b+1,\omega+b+2,\cdots\}$，其 $\operatorname{MEX}$ 为 $\omega+1$。 可以发现这和 $c=1$ 的情况高度相似。 类似 $c=1$ 可得当 $a<b$ 时，$\operatorname{SG}(a,b,3)=\omega+a+1$。 我们重点讨论 $a=b$ 的情况。 此时子状态集合为 $\{0,1,2,\cdots\} \cup \{\omega,\omega+1,\omega+2,\cdots\}$，此时的 SG 值已无法用任何 $\omega+x$ 形式的数表示。 那咋办？考虑仿照 $c=1$ 的做法，把这个 $x$ 替换成 $\omega$，那么此时的 SG 值就可以用 $\omega+\omega=\omega\cdot 2$ 表示了。 现在我们构造出的记号大小顺序为： $$0<1<2<\cdots<\omega<\omega+1<\omega+2<\cdots<\omega\cdot 2$$ 所以 $\operatorname{SG}(b,b,3)=\omega\cdot 2$。 那么以此类推： $\operatorname{SG}(b+1,b,3)=\operatorname{MEX}(\{0,1,2,\cdots\} \cup \{\omega,\omega+1,\omega+2,\cdots\} \cup \{\omega\cdot 2\})=\omega\cdot 2+1$。 $\operatorname{SG}(b+2,b,3)=\operatorname{MEX}(\{0,1,2,\cdots\} \cup \{\omega,\omega+1,\omega+2,\cdots\} \cup \{\omega\cdot 2,\omega\cdot 2+1\})=\omega\cdot 2+2$。 于是 $\operatorname{SG}(a,b,3)=\begin{cases}\omega+a+1&a<b\\\omega\cdot 2+a-b&a\ge b\end{cases}$。 --- $c=4,5$ 和 $c=2,3$ 基本相同，易得 $\operatorname{SG}(a,b,4)=\omega\cdot 2+a+1$， $\operatorname{SG}(a,b,5)=\begin{cases}\omega\cdot 2+a+1&a<b\\\omega\cdot 3+a-b&a\ge b\end{cases}$ 读者自证不难。 讲到这里，相信大家已经看出了规律： - 当 $c=0$ 时，$\operatorname{SG}(a,b,0)=a$。 - 当 $c=1$ 时，$\operatorname{SG}(a,b,1)=\begin{cases}a&a<b\\\omega+a-b&a\ge b\end{cases}$。 - 当 $c=2m(m>0)$ 时，$\operatorname{SG}(a,b,c)=\omega\cdot m+a+1$。 - 当 $c=2m+1(m>0)$ 时，$\operatorname{SG}(a,b,c)=\begin{cases}\omega\cdot m+a+1&a<b\\\omega\cdot (m+1)+a-b&a\ge b\end{cases}$。 上述结论可以按照 $c$ 归纳证明，证明过程与上面 $c=2,3$ 的分析完全一致，这里略去重复部分。 将每个游戏机的 SG 值异或起来就做完了。 可是 $\omega$ 怎么异或？ ### 胜负判定 注意到普通 Nim 中，胜负判定是由数值的异或和决定的。 于是考虑构造一个新的异或 ${}^1$：定义 $(\omega\cdot a+b)\oplus(\omega\cdot c +d)=\omega\cdot (a\oplus c)+(b\oplus d)$。 我们猜测，先手必败当且仅当所有 SG 值的异或和恰好为 $0$。事实证明的确如此，以下为详细证明。 ::::info[证明]{open} 假设第 $i$ 个游戏机的 SG 值为 $\omega\cdot p_i+q_i$，$\operatorname{MEX}$ 的性质告诉我们，它可以转移到所有 SG 值更小的子状态 $\omega\cdot p^{\prime}_i+q^{\prime}_i$，其中 $p^{\prime}_i<p_i$ 或 $p^{\prime}_i=p_i,q^{\prime}_i<q_i$。 设 $p_i$ 的异或和为 $P$，$q_i$ 的异或和为 $Q$，则当 $P=Q=0$ 时为必败状态。 先证必败状态的所有子状态必为必胜状态。采用反证法，假设存在一个 $x$ 和对应的 $p^{\prime}_x$ 和 $q^{\prime}_x$ 满足操作后其为必败态，则由异或的性质得： - $P=P\oplus p_x\oplus p^{\prime}_x=0$。 - $Q=Q\oplus q_x\oplus q^{\prime}_x=0$。 于是 $p_x\oplus p^{\prime}_x=q_x\oplus q^{\prime}_x=0$，$p_x=p^{\prime}_x$ 且 $q_x=q^{\prime}_x$，根据 $\operatorname{MEX}$ 的定义，不存在任意一个子状态的 SG 值与当前状态相同，矛盾。 故必败状态的所有子状态必为必胜状态。 再证必胜状态存在至少一个子状态为必败状态。 先给出一个普通 Nim 游戏的引理： > 一个非负整数序列 $a_1,a_2,\cdots,a_n$，满足 $\bigoplus\limits_{i=1}^{n}a_i\neq 0$，则一定存在一个 $x$ 和对应的 $0 \le a^{\prime}_x<a_x$，满足 $\bigoplus\limits_{i=1}^{n}a_i\oplus a^{\prime}_x\oplus a_x=0$。 > 证明可以上网去搜，这里略过。 然后分类讨论： - $P\neq 0$。根据引理以及 $\operatorname{MEX}$ 的性质，一定存在一个 $x$ 和对应的 $0\le p^{\prime}_x<p_x$ 满足 $P\oplus p^{\prime}_x\oplus p_x=0$，同时无论选择哪个 $q^{\prime}_x$，根据 $\omega$ 的性质都有 $\omega\cdot p^{\prime}_x+q^{\prime}_x<\omega\cdot p_x+q_x$，$\operatorname{MEX}$ 的性质告诉我们该操作一定合法，所以将 $p_x$ 修改成对应的 $p^{\prime}_x$ 并将 $q^{\prime}_x$ 置为 $Q\oplus q_x$ 即可。 - $P=0$，此时 $Q\neq 0$。我们保持 $p$ 不变，根据引理，一定存在一个 $x$ 和对应的 $0\le q^{\prime}_x<q_x$ 满足 $Q\oplus q^{\prime}_x\oplus q_x=0$。根据证明开头提到的 $\operatorname{MEX}$ 的性质，这个操作一定是合法的，将这个 $q_x$ 修改成 $q^{\prime}_x$ 即可。 综上所述，先手必败当且仅当所有 SG 值的异或和恰好为 $0$，证毕。 :::: 综上，我们在 $O(n)$ 的时间复杂度内解决了此题，那这篇文章就可以收工了……吗？ --- 先别急，我们刚才为了让 $\operatorname{MEX}$ 继续工作，一路构造出了 $$ 0,1,2,\cdots,\omega,\omega+1,\omega+2,\cdots,\omega\cdot 2,\cdots $$ 看起来多少有点野生数学的味道。 不过这些东西当然不是为了这道题临时编出来的。事实上，它们早就有一个统一的名字——**序数（Ordinal Number）**。 而我们刚才做的事情，本质上就是把普通 SG 函数的值域从非负整数推广到了序数。 ## 无穷序数的介绍 ### 从 $\omega$ 开始 记 $a\rightarrow b$ 表示将 $a$ 标号为 $b$。 下面为了方便理解，我们只考虑已经按照某种顺序排好的集合，并用“编号”来描述其中各元素所处的位置。 我们最常使用的自然数，其实就是最简单的序数。 但需要注意的是：直观上，可以把序数理解成描述“排列位置”的对象；更准确地说，它描述的是顺序类型，而不是单纯的元素数量。 例如，一个集合 $\{a,b,c\}(a< b< c)$，如果我将这个集合从 $0$ 开始编号，$a\rightarrow 0$，$b\rightarrow 1$，$c\rightarrow 2$，假设我往后面再放一个数 $x$（称之为“虚拟元素”${}^2$），那么显然 $x\rightarrow 3$，这个集合对应的序数就是 $3$。 考虑集合 $\{0,1,2,\cdots\}$，如果我往后面再放一个“虚拟元素”，那么这个新位置已经排在所有有限编号之后，我们把这个新编号记作 $\omega$。自然地，这个集合的序数就是 $\omega$ 了。 如果我往刚刚提到的这个集合里再放一个元素 $x$，那么 $x$ 的编号就是 $\omega$，自然地，“虚拟元素”的编号就是 $\omega+1$。 同理，如果我又放了一个 $y\rightarrow \omega+1$，那么“虚拟元素”的编号就是 $\omega+2$。 如果我们在原来的 $\omega$ 段后面，再接上一整段同样具有序型 $\omega$ 的集合，那么整个集合会变成 $\{0,1,2,\cdots,x,y,z,\cdots\}$，此时“虚拟元素”的编号会超越一切 $\omega+a$，那就自然地可以想到将这个元素的编号设为 $\omega+\omega=\omega\cdot2$，那么这个集合的序数就是 $\omega\cdot2$ 了。 以此类推，我们会有 $\omega\cdot3,\omega\cdot4,\omega\cdot5$ 等等，这恰好对应了题解部分里出现的 SG 值。 尽管序数是表示编号的，但是序数其实也有加法，并且这种加法不满足交换律。 依旧以集合入手，我们可以将序数的加法理解成：把两个集合首尾相接，并规定前一个集合中的所有元素都排在后一个集合之前。 例如 $3+2$ 就可以理解成：在一个原本对应序数为 $3$ 集合 $\{a,b,c\}$ 后接上对应序数为 $2$ 的集合 $\{d,e\}$，使其序数变为 $3+2=5$。 当两个序数都是有限序数时，序数加法与普通整数加法一致，因此满足交换律。 可当加法中出现 $\omega$，事情就变得不一样了。 先考虑 $\omega+1$，这相当于在 $\{0,1,\cdots\}$（序数为 $\omega$）中再添加一个 $x$，易知 $x\rightarrow \omega$，此时因为 $\omega$ 已经被占用了，所以你只能将“虚拟元素”编号为 $\omega+1$。 再考虑 $1+\omega$，这相当于在序数为 $1$ 的集合 $\{x\}$（序数为 $1$）的后面接上集合 $\{0,1,\cdots\}$。 我只需要将每个元素重编号，具体地，$x\rightarrow0,0\rightarrow1,1\rightarrow2,\cdots$，那么这些编号都会是非负整数而不是 $\omega$，所以“虚拟元素”的编号就是 $\omega$。 到这里就可以发现，$1+\omega=\omega<\omega+1$，同理得到 $2\cdot \omega=\omega<\omega\cdot2$。 理由是 $2\cdot\omega$ 可以通过 将第 $n$ 组（从 $0$ 开始编号）序数为 $2$ 的块 $\{x,y\}$ 编号为 $2n$ 和 $2n+1$，此时每个元素都有非负整数的编号，故序数为 $\omega$。 但 $\omega\cdot2$ 表示先完整放上一个 $\omega$ 块，再接上一个 $\omega$ 块，前一个块的序数已经是 $\omega$ 了，所以第二个块只能从 $\omega$ 开始编号，自然会比 $\omega$ 要大。 ### 一些更大的序数 既然有 $\omega+\omega$，那我们也可以有 $\omega\cdot\omega=\omega^2$，可以理解为把 $\omega$ 个顺序类型为 $\omega$ 的块依次首尾相接，此时所有形如 $\omega\cdot a+b\quad (a,b\in \mathbb{Z}_{\ge0})$ 的编号都已出现，即 $\omega^2$ 排在它们之后。 类似的，我们也有 $\omega^2+1,\omega^2+2, \cdots ,\omega^2+\omega,\cdots,\omega^2\cdot 2,\cdots,\omega^2\cdot\omega=\omega^3$。 能不能再给力一点？ 考虑扩大指数，这样我们就有 $$\omega^4,\omega^5,\cdots,\omega^\omega$$ 继续扩大指数： $$\omega^{\omega+1},\cdots,\omega^{\omega\cdot2}\cdots,\omega^{\omega^2}\cdots,\omega^{\omega^{\omega}}$$ 如果我们一直这样向上叠 $\omega$，我们会得到 $\omega^{\omega^{\omega^{\omega}}},\omega^{\omega^{\omega^{\omega^\omega}}}$，这些有限高度的幂塔会不断变大，我们把它们的上确界记作 $\varepsilon_0$。 这个突然冒出来的 $\varepsilon_0$ 是啥？它恰好是最小满足 $\omega^\alpha=\alpha$ 的序数 $\alpha$。你可以把它理解成“$\omega$ 的 $\omega$ 层幂塔”。 --- 如果继续往后，还可以定义 $\varepsilon_1,\varepsilon_2,\cdots$，甚至更大的序数，但这些已经远远超出了这篇文章讨论的范围。 虽然说这道题真正用到的甚至只有 $\omega\cdot a+b$ 这一小段，但它已经足够把普通 SG 从有限整数带进无穷序数了。 至于更大的序数，就留到以后真的遇到需要它们的题时再说吧。 ## 注释 ${}^1$：这个运算并不是临时构造出来的，它恰好对应序数的 Nim 和（Nim-Sum），在本题只出现 $\omega\cdot a+b$ 的情况下，就是分别对系数 $a,b$ 做异或。 ${}^2$：仅为辅助理解，它的编号表示的是前面整个集合的顺序类型。