自动搬运

查看原文

来自洛谷，原作者为

	Sooke 做被自己雪藏的耳廓狐 | https://codeforces.com/profile/Sulfox

搬运于2025-08-24 21:34:30，当前版本为作者最后更新于2019-04-02 19:40:23，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

前言

本文将对此题的关键结论进行粗略证明。似乎此前都只有找规律、而没有提到证明的题解？

---

预备

前置知识：SG 函数。篇幅关系就不扯了。

$f(x)$ 为 $x$ 的二进制末尾首个 $0$ 的出现位置（标号从 $0$ 开始）。例如 $f(5) = (101)_2 = 1$ 。

$\mathrm{sg}(x,\ y)$ 为一组分别有 $x + 1,\,y + 1$ 个石子的 $\mathrm{sg}$ 值。注意有 $+1$ 。

$S_z$ 表示满足 $x + y + 1 = z$ 的 $\mathrm{sg}(x,\,y)$ 构成的自然数集合。特别地，$S_0 = \varnothing$ 。

---

引理

引理 $1$ ：$\mathrm{sg}(0,\,0) = 0$ 。

终止局面的 $\mathrm{sg}$ 值为 $0$ 。

引理 $2$ ：$\mathrm{sg}(x,\,y) = \mathrm{mex}(S_x \cup S_y)$ 。

SG 函数经典结论。后继局面可以分割 $x + 1$ 或 $y + 1$ 。注意事先的定义，$S_x$ 不是 $S_{x-1}$ 或 $S_{x+1}$ 。

---

结论

可能要叫“命题”？既然都知道了就当结论吧。（数学不好）

结论 $1$ ：$S_z$ 等同于 $z$ 二进制下 $1$ 的位置集合。例如 $S_5 = \{0,\,2\}$ 。

辅助结论。

结论 $2$ ：$\mathrm{sg}(x,\,y) = f(x\ |\ y)$ 。例如 $\mathrm{sg}(1,\,4) = f(5) = 1$ 。

关键结论。

---

证明

考虑归纳法证明以上两个结论。即逐步放大 $z$ ，证明该 $z$ 下结论 $1$ 及满足 $x + y = z$ 的结论 $2$ 的正确性。

根据引理 $1$ ，结论 $2$ 在 $z = 0$ 时正确。假设已证 $z - 1$ 时结论 $2$ 的正确性，考虑 $S_{z}$ 包含元素 $p$ 的条件。

由定义和结论 $2$ 可知，需存在 $x + y = z - 1$ 且 $f(x\ |\ y)=p$ ，得 $x,\,y$ 在二进制下，第 $p$ 位都为 $0$ ，第 $0 \sim p - 1$ 位都至少有一个是 $1$ 。

考虑最劣极限，第 $0 \sim p - 1$ 位只有其中一个是 $1$ ，由于交换律，这些 $1$ 都在 $x$ 中是没有关系的。

此时，因为 $x + y + 1 = z$ ，模拟二进制运算（$+ 1$ 会导致上述所有 $1$ 进位到第 $p$ 位），$z$ 的第 $p$ 位为 $1$ ，第 $0 \sim p - 1$ 位为 $0$ 。

反观最优极限下，$y$ 的第 $0 \sim p - 1$ 位也都是 $1$ ，实际上，这些位不管怎么安排 $0,\,1$ ，丝毫不影响 $z$ 的第 $p$ 位为 $1$ 的事实（见上方粗体文字）。

故 $z$ 二进制第 $p$ 位为 $0$ 时，$S_{z}$ 不可能包含元素 $p$ 。为 $1$ 时，显然令 $x = 2^{p} - 1,\,y = z - 2^p$ 即可满足条件。

既然有了 $z$ 时结论 $1$ 的正确性，不妨以此推出 $z$ 时结论 $2$ 的正确性。

$$\mathrm{sg}(x,\,y) = \mathrm{mex}(S_x \cup S_y)=\mathrm{mex}(S_{x\ |\ y}) = f(x\ |\ y) $$

根据结论 $1$ ，$S$ 是 $1$ 的位置集合，易证 $S_x \cup S_y = S_{x\ |\ y}$ ，并且 $x\ |\ y \leqslant x + y = z$ 在已证范围内。同时，$\mathrm{mex}$ 是最小未出现自然数，配上位置集合，正好就是 $f$ 的定义。故可证任意 $z$ 下两个结论。