前置知识
有向图游戏概念。
单个有向图游戏中 \(\textrm{SG}\) 函数的求值（\(\textrm{mex}\) 运算）。
以上内容请自行查阅，这里不会多说。
前言
本文受启发于 OI Wiki，采用相同的数学归纳法进行证明，但对计算的原理进行了补充，也补足了一些细节。
网上许多 \(\textrm{SG}\) 定理的证明只是对是否满足必胜必败展开证明。但本文实际上要证明其异或和一定等于 \(\textrm{SG}\) 函数的值。
另外，在本文用 \(\oplus\) 代表 \(\textrm{xor}\) 运算。
定理
\(\textrm{SG}\) 定理：
\[\textrm{SG}(A_1+A_2+...+A_n) = \textrm{SG}(A_1) \oplus \textrm{SG}(A_2) \oplus ... \oplus \textrm{SG}(A_n) \]其中 \(A_i\) 为一个任意有向图游戏局面。
证明
根据数学归纳法，结合 \(\textrm{SG}\) 函数本身的性质可知：
若有：
\[\textrm{SG}(A+B) = \textrm{SG}(A) \oplus \textrm{SG}(B) \]则显然原命题成立。
设局面 \(A\) 的一个后继为 \(A'\)， 局面 \(B\) 的一个后继为 \(B'\)， \(\textrm{SG}(A) = a\)， \(\textrm{SG}(B) = b\)， \(\textrm{SG}(A') = a'\)， \(\textrm{SG}(B') = b'\)。
根据 \(\textrm{mex}\) 的性质可知：
\(a'\) 可以取遍 \([0,a)\)， 以及一些大于 \(a\) 的值。
\(b'\) 可以取遍 \(\,[0,b)\)， 以及一些大于 \(b\) 的值。
这里我们发现，若先手选择了一个局面的后继使后继局面的 \(\textrm{SG}\) 函数值大于当前局面本身的 \(\textrm{SG}\) 函数值，后手显然可以让局面的 \(\textrm{SG}\) 函数值再次等于当前的局面的 \(\textrm{SG}\) 函数值。所以让后继大于当前局面的 \(\textrm{SG}\) 函数值是没有意义的。
所以我们接下来对局面后继的选择只会是 \(\textrm{SG} \) 函数值小于原局面的 \(\textrm{SG}\) 函数值的后继。
我们采用数学归纳法：
1.
当 \(a=b=0\) 时，显然命题成立。
2.
假设局面 \((A'+B)\) 和局面 \((A+B')\) 都满足命题。
所以有：
\(\textrm{SG}(A'+B)\) 取遍 \([0,a' \oplus b)\)。
\(\textrm{SG}(A+B')\) 取遍 \([0,a \oplus b')\)。
设 \(c=a \oplus b=\sum_{i=1}^t{2^{P_i}}\)，且满足 \(P_i>P_{i+1}\)。
因为 \(a'<a\)，所以有 \(a' \oplus b \ne a \oplus b\) 即 \(a' \oplus b \ne c\)。
因为 \(\,b'<b\)，所以有 \(a \oplus b' \ne a \oplus b\) 即 \(a \oplus b' \ne c\)。
我们找到 \(c\) 在二进制下的最高位 \(P_i\)，这时一定有一个数的这一位为 \(1\)（不妨为 \(a\)），另一个数的这一位为 \(0\)（不妨为 \(b\)）。
所以\(a' \oplus b\) 取值集合与 \(a \oplus b'\) 取值集合的并集一定包含 \([0,2^{P_i})\)。然后我们将 \(a'\) 的第 \(P_i\) 位强制设为 \(1\)，只看所有数的二进制位数低于\(P_i\)的二进制段，再用同样的方法计算取值集合并集。
这是我们会发现算出了这些集合:
\[[0,2^{P_1}),[0,2^{P_2}),...,[0,2^{P_t}) \]但是每个集合都要加上高位上强制为 \(1\) 的位置，所以取值集合并集实际为
\[[0,2^{P_1}),[2^{P_1},2^{P_1} + 2^{P_2}),...,[\sum_{i=1}^{t-1}{2^{P_i}},\sum_{i=1}^t{2^{P_i}}) \]上述集合的并集为：
\[[0,\sum_{i=1}^t{2^{P_i}}) \]又因为：
\[\sum_{i=1}^t{2^{P_i}}=c \]所以 \(a' \oplus b\) 与 \(a \oplus b'\)的取值并集取遍：
\[[0,c) \]又因为 \(a' \oplus b \ne c,a \oplus b' \ne c\)，所以：
\[c=\mathrm{mex}_{a'<a,b'<b}\{ a' \oplus b , a \oplus b' \} \]所以有：
\[\textrm{SG}(A+B) =\mathrm{mex}_{a'<a,b'<b}\{ a' \oplus b , a \oplus b' \} = c=a \oplus b = \textrm{SG}(A) \oplus \textrm{SG}(B) \]所以当该局面后继的 \(\textrm{SG}\) 函数满足命题时，该局面的 \(\textrm{SG}\) 函数满足命题。
综上，由 1. 与 2. 并根据数学归纳法，证得：
\[\textrm{SG}(A+B) = \textrm{SG}(A) \oplus \textrm{SG}(B) \]即原命题成立。
END
完力（喜）。
标签：局面,函数,定理,证明,textrm,oplus,后继,SG From： https://www.cnblogs.com/imcaigou/p/17883947.html