题解 P2148 【[SDOI2009]E&D】

### 前言 本文将对此题的关键结论进行粗略证明。似乎此前都只有找规律、而没有提到证明的题解？ ------ ### 预备 前置知识：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$ 下两个结论。