前言
「经过数学家的不懈努力」是 Nim 积相关题解不可避免的一环……吗？
本文旨在勾勒部分 Nim 积性质的证明，有了这些性质后数据结构优化是不难的，可以参考其它题解。
更具体的介绍可以参考这篇文章（仍在更新中！）。
本文参考了《On Numbers And Games》的第六章。
对于不理解何为「序数」的读者，可以自行将文中所有「序数」换为「非负整数」。
如果你学过一定的抽象代数，你可以把文中的「对加法封闭」「对加法、乘法封闭」「对四则运算封闭」「所有多项式方程均有解」替换成「是群」「是环」「是域」「代数闭」。（因为异或意义下 \alpha+\alpha=0，一个数自然有相反数，因此可以不考虑减法）
在集合论中，冯诺依曼表示法的序数 \alpha 就是集合 \{\beta|\beta<\alpha\}，其中 \beta 是序数。本文不区分这两者。例如，当我们说到「2 对四则运算封闭」的时候，也就是说「\{0,1\}（在异或和 Nim 积意义下）对四则运算封闭。」
本文中，方括号 [] 中的运算为通常的序数运算，而其外部的运算为 Nim 运算。
引子
假如我们想在所有序数上定义一个加法和一个乘法，使得它们对四则运算封闭，并且它“字典序最小”（这个概念并不严格），应该怎么做？
先考虑加法吧。
$1+1=0$ 不会有问题，不就是特征【最小的 $n$ 满足所有数加 $n$ 遍等于 $0$】为 $2$ 嘛。
$1+2$ 是几？它不能等于 $1+1=0$，$1+0=1$，$0+2=2$，否则就和域有加法逆元（因此有消去律）矛盾了。因此 $1+2=3$。
这启发我们递归地定义
$$
\alpha+\beta=\operatorname{mex}(\{\alpha+\delta|\delta<\beta\}\cup\{\gamma+\beta|\gamma<\beta\})
$$
据此列出表格
$$
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
+&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline
0&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline
1&1&0&3&2&5&4&7&6&9&8&11&10&13&12&15&14\\\hline
2&2&3&0&1&6&7&4&5&10&11&8&9&14&15&12&13\\\hline
3&3&2&1&0&7&6&5&4&11&10&9&8&15&14&13&12\\\hline
4&4&5&6&7&0&1&2&3&12&13&14&15&8&9&10&11\\\hline
5&5&4&7&6&1&0&3&2&13&12&15&14&9&8&11&10\\\hline
6&6&7&4&5&2&3&0&1&14&15&12&13&10&11&8&9\\\hline
7&7&6&5&4&3&2&1&0&15&14&13&12&11&10&9&8\\\hline
8&8&9&10&11&12&13&14&15&0&1&2&3&4&5&6&7\\\hline
9&9&8&11&10&13&12&15&14&1&0&3&2&5&4&7&6\\\hline
10&10&11&8&9&14&15&12&13&2&3&0&1&6&7&4&5\\\hline
11&11&10&9&8&15&14&13&12&3&2&1&0&7&6&5&4\\\hline
12&12&13&14&15&8&9&10&11&4&5&6&7&0&1&2&3\\\hline
13&13&12&15&14&9&8&11&10&5&4&7&6&1&0&3&2\\\hline
14&14&15&12&13&10&11&8&9&6&7&4&5&2&3&0&1\\\hline
15&15&14&13&12&11&10&9&8&7&6&5&4&3&2&1&0\\\hline
\end{array}
$$
稍微验证一下发现它确实符合交换律、结合律……等等这不就是异或吗？怎么证明呢？
还是先来考虑一下乘法吧。首先 $0\alpha=\alpha0=0$，那 $1\times1$ 就不能是 $0$ 了，那就 $1$ 吧。好，$1$ 就是幺元了！那么 $1\alpha=\alpha1=\alpha$。$2\times2$ 等于多少？可以是 $1$ 吗？这样的话 $(2+1)\times(2+1)=2\times2+1\times2+2\times1+1\times1=0$，似乎不太对。可以是 $2$ 吗？$1\times2$ 已经是 $2$ 了啊。那就 $3$？暂时看起来没什么问题。
等等我们发现了什么……$(x+y)^2=x^2+y^2$，因此两个数的平方不能相同！这个性质很优美诶。
因为 $3=1+2$，由分配律 $3$ 相关的都做完了。
$2\times 4$ 是多少？显然不能为 $2\times0=0,2\times1=2,2\times2=3,2\times3=1$。如果是 $4+x(0\le x<4)$ 的话，那 $2\times4=4+x$ 得 $(2+1)\times4=x$，$3\times4<4$ 的话也不行（因为 $3\times0=0,3\times1=3,3\times2=1,3\times3=2$）。那么就最小是 $2\times4=8$ 了。
$3\times4=2\times4+1\times4=8+4=12$。
那 $4\times 4$ 是多少？根据之前的结果，它不能等于 $0^2=0,1^2=1,2^2=3,3^2=3,1\times4=4$。能等于 $5$ 吗？这意味着 $4$ 是 $x^2+x+1=0$ 的根。可是这是 $(x+2)(x+3)=0$！而 $(4+2)\times(4+3)$ 不能为 $0$。因此 $5$ 也不行。那就 $6$ 吧。先看着……
好像导致 $a\times b=x$ 矛盾的点都是 $(a+a')(b+b')=0$？那就让这些全都不为 $0$ 即可。这启发我们定义
$$
\alpha\beta=\operatorname{mex}\{\alpha\delta+\gamma\beta+\gamma\delta|\gamma<\alpha,\delta<\beta\}
$$
据此列出表格
$$
\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|}
\times&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline
0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0&0\\\hline
1&0&1&2&3&4&5&6&7&8&9&10&11&12&13&14&15\\\hline
2&0&2&3&1&8&10&11&9&12&14&15&13&4&6&7&5\\\hline
3&0&3&1&2&12&15&13&14&4&7&5&6&8&11&9&10\\\hline
4&0&4&8&12&6&2&14&10&11&15&3&7&13&9&5&1\\\hline
5&0&5&10&15&2&7&8&13&3&6&9&12&1&4&11&14\\\hline
6&0&6&11&13&14&8&5&3&7&1&12&10&9&15&2&4\\\hline
7&0&7&9&14&10&13&3&4&15&8&6&1&5&2&12&11\\\hline
8&0&8&12&4&11&3&7&15&13&5&1&9&6&14&10&2\\\hline
9&0&9&14&7&15&6&1&8&5&12&11&2&10&3&4&13\\\hline
10&0&10&15&5&3&9&12&6&1&11&14&4&2&8&13&7\\\hline
11&0&11&13&6&7&12&10&1&9&2&4&15&14&5&3&8\\\hline
12&0&12&4&8&13&1&9&5&6&10&2&14&11&7&15&3\\\hline
13&0&13&6&11&9&4&15&2&14&3&8&5&7&10&1&12\\\hline
14&0&14&7&9&5&11&2&12&10&4&13&3&15&1&8&6\\\hline
15&0&15&5&10&1&14&4&11&2&13&7&8&3&12&6&9\\\hline
\end{array}
$$
稍微验证一下发现它确实符合交换律、分配律……而且似乎每 $[2^{2^N}]$ 以内对乘法封闭？而因为消去律一定有一个 $\beta$ 满足 $\alpha\beta=1$，所以就对四则运算封闭了……？怎么证明呢。
## 加减乘除
**定义 .** 对于任意序数 $\alpha,\beta$，我们递归定义它们的**异或**（Nim 和）为
$$
\alpha+\beta=\operatorname{mex}(\{\alpha+\delta|\delta<\beta\}\cup\{\gamma+\beta|\gamma<\beta\})
$$
**定义 .** 对于任意序数 $\alpha,\beta$，我们递归定义它们的 Nim 积为
$$
\alpha\beta=\operatorname{mex}\{\alpha\delta+\gamma\beta+\gamma\delta|\gamma<\alpha,\delta<\beta\}
$$
我们记 $\alpha^*$ 为一变量，它能取值所有 $<\alpha$ 的序数和部分 $>\alpha$ 的序数。（即，其取值范围的 $\operatorname{mex}$ 为 $\alpha$）如果 $\alpha$ 的定义式/计算式为 $\operatorname{mex}(S)$，称 $S$ 的所有元素为 $\alpha$ 的排除项。
**定理 .** 对于任意序数 $\alpha,\beta,\gamma$，$\alpha+\beta=\alpha+\gamma$ 当且仅当 $\beta=\gamma$。
**证明 .** 充分性显然。必要性考虑反证。若 $\beta\neq \gamma$，不妨设 $\beta<\gamma$，则 $\alpha+\beta$ 为 $\alpha+\gamma$ 的一排除项，矛盾。
**定理 .**（加法的冗余定理）对于任意序数 $\alpha,\beta$，
$$
\alpha+\beta=\operatorname{mex}(\{\alpha+\beta^*|\beta^*\}\cup\{\alpha^*+\beta|\alpha^*\})
$$
**证明 .** 显然 $\alpha+\beta$ 的所有排除项都被排除了，而其它的元素排除项含有 $\alpha+\beta$，故右侧取值为 $(\alpha+\beta)^*$，即 $\operatorname{mex}$ 为 $\alpha+\beta$。
**定理 .** 对于任意序数 $\alpha,\beta,\gamma$，有
1. $\alpha+0=\alpha
-
\alpha+\beta=\beta+\alpha
-
(\alpha+\beta)+\gamma=\alpha+(\beta+\gamma)
-
\alpha+\alpha=0
证明 . 直接归纳即可。注意第三条要用到冗余定理。
推论 . （多个数的加法计算式）在证明第三条的归纳过程中，我们可以用归纳类似地证明：对于任何 n 个序数 \alpha_1,\alpha_2,\cdots,\alpha_n，有：
\sum_{i=1}^n\alpha_i=\operatorname{mex}\bigcup\limits_{i=1}^n\{\sum_{j=1}^n\begin{cases}\alpha&j=i\\\alpha_j&j\neq i\end{cases}|\alpha<\alpha_j\}
定理 . 对于任意序数 \alpha，有 \alpha0=0\alpha=0。
证明. \alpha0 和 0\alpha 均无排除项，即证。
定理 . 对于任意序数 \alpha,\beta,\gamma，\alpha\beta=\alpha\gamma 当且仅当 \beta=\gamma 或 \alpha=0。
证明. 充分性显然。必要性考虑反证。若 \beta\neq \gamma，不妨设 \beta<\gamma，而 0<\alpha，故 \alpha\gamma 的排除项有 \alpha\beta+0\gamma+0\beta=\alpha\beta，矛盾。
定理 .（乘法的冗余定理）对于任意序数 \alpha,\beta，有
\alpha\beta=\operatorname{mex}\{\alpha\beta^*+\alpha^*\beta+\alpha^*\beta^*|\alpha^*,\beta^*\}
证明 . 显然 \alpha\beta 的排除项都被排除了。因此我们只需证 \alpha\beta\neq \alpha\beta^*+\alpha^*\beta+\alpha^*\beta^* 即可。根据异或的自逆，这等价于 \alpha\beta+\alpha\beta^*+\alpha^*\beta+\alpha^*\beta^*\neq 0。显然，其它三者之和为最大的一者的排除项，即证。
定理 . 对于任意序数 \alpha,\beta,\gamma，有
-
\alpha1=\alpha
-
\alpha\beta=\beta\alpha
-
(\alpha\beta)\gamma=\alpha(\beta\gamma)
-
\alpha(\beta+\gamma)=\alpha\beta+\alpha\gamma
证明 . 直接归纳即可。注意第三条和第四条要用到冗余定理。
推论 .（多个数的乘法计算式）在证明第三条的归纳过程中，我们可以用归纳类似地证明：对于任何 n 个序数 \alpha_1,\alpha_2,\cdots,\alpha_n，有：
\prod_{i=1}^n\alpha_i=\operatorname{mex}\{\sum_{I\subsetneq\{1,2,\cdots,n\}}\prod_{j=1}^n\begin{cases}\alpha_j&j\in I\\\beta_j&j\not\in I\end{cases}|\beta_j<\alpha_j\}
定义 . 对于任意序数 \alpha>0，定义
S=\{0\}\cup\{\gamma^{-1}(1+(\alpha+\gamma)\delta)|0<\gamma<\alpha,\delta\in S\}
则定义 \alpha^{-1}=\operatorname{mex}(S)。对于任意序数 \alpha,\beta，定义 \alpha/\beta=\dfrac\alpha\beta=\alpha\beta^{-1}。
（注：这个 S 是一个递归的定义，即 S 包含了上述操作在有限步以内能生成的所有数。）
定理 .
- 对于任何序数 \alpha>0，设 \beta 为 \alpha^{-1} 的一排除项，则 \alpha\beta\neq 1。
- 对于任何序数 \alpha>0，设 \beta 为 \alpha\alpha^{-1} 的一（冗余）排除项，\beta\neq 1。
- 对于任何序数 \alpha>0，\alpha\alpha^{-1}=1。
证明 . 考虑归纳。
- 若 \beta=0 显然，否则设 \beta=\gamma^{-1}(1+(\alpha+\gamma)\delta)。则 1+\alpha\beta=\gamma\gamma^{-1}+\alpha\beta=\gamma^{-1}(\alpha+\gamma+\alpha(\alpha+\gamma)\delta)=\gamma^{-1}(\alpha+\gamma)(1+\alpha\delta)。显然 \gamma^{-1}\neq 0，又因 \gamma<\alpha 有 \alpha+\gamma 不为 0，根据归纳假设又有，1+\alpha\delta 不为 0，故乘积不为 0，即证。
- 设 \beta=\gamma\alpha^{-1}+\alpha(\alpha^{-1})^*+\gamma(\alpha^{-1})^*，其中 (\alpha^{-1})^* 为 \alpha^{-1} 的一排除项。若 \gamma 等于 0，这就是前一条所证的。否则因为 \lambda=\gamma^{-1}(1+(\alpha+\gamma)(\alpha^{-1})^*) 也为 \alpha^{-1} 的一排除项，又因为 \gamma\gamma^{-1}=1，故 \beta=1+\gamma(\alpha^{-1}+\lambda)\neq 1。
- 显然 \alpha\alpha^{-1}\neq 0，因为 \alpha^{-1}\neq 0。而由 2 得 \alpha\alpha^{-1} 的排除项不含 1，即证。
扩张，扩张，扩张
定理 . 设 \Delta 不对加法封闭，则 \Delta=\alpha+\beta，其中 (\alpha,\beta) 为字典序最小的一对 \Delta 的元素满足 \alpha+\beta 不在 \Delta 中。
证明 . 显然 \alpha+\beta\ge \Delta，但是 \alpha+\beta 的排除项都在 \Delta 中。（这是因为字典序更小了）即证。
定理 . 设 \Delta 对加法封闭，则对于任意 \alpha 和 \beta\in \Delta 有 [\Delta\alpha]+\beta=[\Delta\alpha+\beta]。
（例. 4=\{0,1,2,3\} 对加法封闭，故 8+3=[4\times2]+3=[4\times 2+3]=11。）
证明 . 考虑归纳。左侧的排除项为：
根据归纳假设，左侧即为 [\Delta\alpha']+(\beta+\gamma)。而由于 \Delta 形成一个群，\beta+\gamma 恰好能取遍所有的 \gamma'<\Delta！故根据归纳假设，所有的排除项为 [\Delta\alpha'+\gamma'] 和 [\Delta\alpha+\delta]，这恰为所有小于 [\Delta\alpha+\beta] 的数，即证。
定理 . 设 \Delta 对加法封闭但不对乘法封闭，则 \Delta=\alpha\beta，其中 (\alpha,\beta) 为字典序最小的一对 \Delta 的元素满足 \alpha\beta 不在 \Delta 中。
（例. 8 对加法封闭但不对乘法封闭，字典序最小的 (\alpha,\beta)=(2,4)，故 8=2\times4。）
证明 . 显然 \alpha\beta\ge \Delta，但是 \alpha\beta 的排除项都在 \Delta 中。（这是因为字典序更小了，且加法封闭）即证。
定理 . 设 \Delta 对加法和乘法封闭，对加法封闭的 \Gamma\le \Delta 满足 \Gamma 中的非零元都在 \Delta 中有乘法逆元（即与其乘积为 1 的元素），则对于任意 \gamma\in \Gamma，有 \Delta\gamma=[\Delta\gamma]。
（例. 4=\{0,1,2,3\} 对加法和乘法封闭，且 4\le 4 中的所有非零元都在 4 中有逆，故 3\times 4=[3\times4]=12。）
证明 . 考虑归纳。\Delta\gamma 的排除项为 \Delta\alpha+\beta\alpha+\beta\gamma,\beta<\Delta,\alpha<\gamma。只需证对于任何 \alpha<\gamma，有 \Delta\alpha+\beta(\alpha+\gamma) 能取遍所有 [\Delta\alpha+\delta]=[\Delta\alpha]+\delta=\Delta\alpha+\delta。取 \beta=\delta(\alpha+\gamma)^{-1} 即可。
定理 . 设 \Delta 为对四则运算封闭但有些多项式方程无解，设 p(x) 为系数在 \Delta 中，在 \Delta 中没有根的字典序最小的多项式（从高次项到低次项依次比较）。则 p(\Delta)=0。对于任何次数比 p 小的多项式 p'(x)，有 p'(\Delta)=[p'(\Delta)]。
（注意序数乘法可能没有交换律，若 p(x)=\sum \alpha_ix^i，这里 [p'(\Delta)]=\sum \Delta^i\alpha_i，i 从大到小加。）
（例。 4=\{0,1,2,3\} 对四则运算封闭，但是有无根多项式 x^2+x+2=0，故 4^2=4+2=6。）
（注：你问对加、乘封闭但没法做除法的情况去哪里了？事实上有，但是书中的证明有一定问题，而且我们用不到，就咕了。）
证明 . 设 p 的次数为 n。对于任何一个 N，考虑 \Delta^N 的排除项为：
\prod_{i=1}^N\alpha_i=\operatorname{mex}\{\sum_{i=0}^{N-1}\sum_{I\subsetneq\{1,2,\cdots,N\},|I|=i}\Delta^i\prod_{j\not\in I}\beta_j|\beta_j<\alpha_j\}
先归纳地证明若 N<n 则 N 次多项式 p'(x) 有 p'(\Delta)=[p'(\Delta)]。
- 先考虑 \Delta^N。只需证明它的排除项能取遍所有 \sum\limits_{i=0}^{N-1}\Delta^i\gamma_i=[\sum\limits_{i=0}^{N-1}\Delta^i\gamma_i] 即可。考虑多项式 q(x)=x^N+\sum\limits_{i=0}^{N-1} x^i\gamma_i。因为 <n 次多项式均有根，它一定可以因式分解为一次因式。设其根为 \delta_1,\delta_2,\cdots,\delta_n，重根算多次。根据 Vieta 定理，\beta_j=\delta_j 即为所求。
- 再考虑 \Delta^N\delta，其中 \delta\in \Delta。它的排除项为 \{\Delta^N\gamma+q(\Delta)(\gamma+\delta)|\gamma<\delta,\deg q<N,[x^i]q(x)\in \Delta\}。只需证明对于任何 \gamma，q(\Delta)(\gamma+\delta) 能取遍每个 q'(\Delta) 即可。因为 \gamma+\delta\in \Delta，故其有逆元，而根据归纳假设，次数更小的多项式乘 \Delta 的元素正常乘即可，故取 q(x)=q'(x)(\gamma+\delta)^{-1} 即可。
- 再考虑 p'(\Delta),\deg p'=N。根据归纳假设，次数更小的多项式加法是正常算的，故 \Delta^N 为一个群。因此设 p'(x)=x^N\delta+q'(x)，则 p'(\Delta)=\Delta^N\delta+q'(\Delta)=[\Delta^N\delta]+[q'(\Delta)]=[\Delta^N\delta+q'(\Delta)]=[p'(\Delta)]。
再证 p(\Delta)=0。设 p(x)=x^n+q(x)（显然，若最高次项系数不为 1，则系数均乘以其逆元字典序更小）。考虑 \Delta^n。和以上过程类似，比 q(\Delta) 小（等价于字典序小）的均为 \Delta^n 的排除项。但 q(\Delta) 不是，否则根据 Vieta 定理 p 就在 \Delta 内有根了。因此 \Delta^n=q(\Delta)，即 p(\Delta)=0。
定理 . 设 \Delta 对四则运算封闭，且所有多项式方程均有根。则对于任意多项式 p(x) 有 p(\Delta)=[p(\Delta)]。
证明 . 和上述定理类似。
推论 . 设 \Delta 对四则运算封闭，\Delta 不是任何 \Delta 上多项式方程的根。
加法
定理 . 若 \Delta 对加法封闭，则下一个对加法封闭的序数为 [\Delta2]。
证明 . 显然 \{x|x<\Delta\} 和 \{\Delta+x|x<\Delta\} 两两不同，所以至少要包含它们。所以 <[\Delta2] 的不对加法封闭。而因为 [\Delta+x]=\Delta+x，所以 [\Delta2] 对加法封闭。
定理 . 每个序数 \alpha 都可以写成 [2^{\beta_0}+2^{\beta_1}+\cdots+2^{\beta_{n-1}}]，其中 n 有限，\beta 严格递减。且 \alpha=[2^{\beta_0}]+[2^{\beta_1}]+\cdots+[2^{\beta_{n-1}}]。
（例如，6=[2^2+2^1]=[2^2]+[2^1]=4+2。）
（注：这也就说明了加法就是异或。）
证明 . 设 \alpha>0，则取最大的 2^\beta\le \alpha，设 \alpha=[2^\beta+\gamma]，显然 \gamma<2^\beta，故 \alpha=[2^\beta]+\gamma。归纳即可。
扩张（试试看！）
来试着通过扩张的几个定理来扩张，得到一些对四则运算封闭的序数吧！
首先最小的非平凡的肯定是 2=\{0,1\}。我们知道，接下来需要找到一个无解方程。显然一次方程就是除法，不可能无解。二次方程呢？对于有限的对四则运算封闭的 n，如果有一个无解的二次方程，那下一个就是对四则运算封闭的 [n^2]=\{[an+b]|a<n,b<n\}=\{an+b|a<n,b<n\} 了。（记 n 为 \mathbb F_n，这其实就是 \mathbb F_n[x]/p(x)，其中 p(x) 为字典序最小的无根多项式）
定理 . 对于有限的 n，若 n 对四则运算封闭，则对任意 a<n，存在 b<n，b^2=a。
证明 . 显然 c\to c^2(c<n) 为单射，故为满射。
所以不需要考虑 x^2 型的了。那 x^2+x 呢？
定理 . 对于有限的 n>1，若 n 对四则运算封闭，恰有半数 a<n，满足不存在 b<n，b^2+b=a。
证明 . 显然 c^2+c=d^2+d 当且仅当 (c+d)(c+d+1)=0，即 c=d 或 c=d+1，故恰有一半的 c^2+c 能被取到。
因此有限情况的扩张都是 x^2+x+a，于是我们做完了……？等等扩张完还是封闭的吗？显然加、乘是封闭呢。除呢？（其实有更一般的关于扩张的证明，但是这里不必要）
定理 . 对于有限的 n，若 n 对加法、乘法封闭，则 n 对四则运算封闭。
证明 . 设 c\neq 0，则 x\to cx(x<n) 为单射，故为满射，故存在 cx=1。
好，于是我们有：
定理 . 所有有限的对四则运算封闭的序数为：
2,4,16,\cdots,[2^{2^n}],\cdots
其中每一个是上一个的[平方]。
证明 . 刚才所讨论的就是这个。
推论 . 若 k<[2^{2^n}]，则 2^{2^n}k=[2^{2^n}k]。
等等，知道是域有什么用，到底怎么算啊？2\to 4 的过程中，最小的无解方程为 x^2+x+1，故 2^2=2+1=3。4\to 16 的过程中，最小的无解方程为 x^2+x+2，故 4^2=4+2=6。在 16\to 256 的过程中呢？对于每个 x<16 计算 x^2+x，发现恰好是 0\sim 7 各一个……？因此 16^2=16+8=24。
更一般地，我们考虑证明：
定理 .
- 对于任何非负整数 n，若 x<[2^n]，则 x^2<[2^n]。
- 对于任何正整数 x，x 与 x^2 的最高位相同。换言之，若 x<[2^{n+1}]，则 x^2+x<[2^n]。
- 对于任何非负整数 n，\{x^2+x|x<[2^{2^n}]\}=[2^{2^n-1}]
- 对于任何非负整数 n，[2^{2^n}]^2=[\dfrac32\times2^{2^n}]。
证明 . 以下归纳不会出现循环论证交给读者作为练习。
- 因为 (x+y)^2=x^2+y^2，且 [2^n] 是一个群，因此只需证明 x=[2^k] 的情况 x^2<[2^{k+1}] 即可。设 k=\sum [2^{a_i}]，则 x=\prod [2^{2^{a_i}}]。（因为 [2^{2^{a_i}}] 对四则运算封闭，所以乘法和直接乘没区别）因此 x^2=\prod [2^{2^{a_i}}]^2。依归纳假设，这即为 x^2=\prod [2^{2^{a_i}}]+[2^{2^{a_i}-1}]。按照乘法分配律展开后，每一项的[普通]积都不超过 [2^{k}]，因此 Nim 积也不超过 [2^k]（因为 Nim 积的排除项个数为普通积），即小于 [2^{k+1}]，故和小于 [2^{k+1}]。
- 根据 1.，有 y\to y^2 是 [2^n] 到 [2^n] 的双射，同时也是 [2^{n+1}] 到 [2^{n+1}] 的双射，因此是 [2^{n+1}]\backslash [2^n] 到自身的双射，即证。自然推出后半句。
- 之前证明过前者的大小刚好为 [2^{2^n-1}]，而取值范围也在 [2^{2^n-1}] 内，即证。
- 根据 3.，最小需要扩展的多项式为 p(x)=x^2+x+[2^{2^n-1}]，即 [2^{2^n}]^2=[2^{2^n}]+[2^{2^n-1}]=[2^{2^n}+2^{2^n-1}]=[\dfrac 32\times2^{2^n}]。
计算
那么问题来了，我们怎么对 Nim 数进行计算呢？
定理 . 假设位运算的时间复杂度为 O(1)，则存在 O(1) 的算法，给定 a,b<[2^{2^k}]，计算 a+b。
证明 . 之前证明了 a+b 是异或，调用即可。
定理 . 假设位运算的时间复杂度为 O(1)，则存在 O(3^k) 的算法，给定 k,a<[2^{2^k}]，计算 a[2^{2^k-1}]。
证明 . k=0 时可以 O(1) 计算。若 k\ge 1，设 \alpha=[2^{2^k-1}],B=[2^{2^{k-1}}],\beta=[2^{2^{k-1}-1}]，则 \alpha=B\beta。设 a=[Bp+q]=Bp+q，则 a\alpha=aB\beta=\beta B(Bp+q)=B^2\beta p+B\beta q=\beta p(B+\beta)+\beta qB={\color{red}(p+q)\beta}B+{\color{blue}p\beta\beta}。递归计算 L=(p+q)\beta,R_0=p\beta,R=R_0\beta，则答案为 LB+R=[LB+R]。时间复杂度 T(k)=3T(k-1)+O(1)=O(3^k)。
定理 . 假设位运算的时间复杂度为 O(1)，则存在 O(k3^k) 的算法，给定 a,b<[2^{2^k}]，计算 ab。
证明 . k=0 时可以 O(1) 计算。若 k\ge 1，设 B=[2^{2^{k-1}}],\beta=[2^{2^{k-1}-1}]。设 a=pB+q,b=rB+s，则 ab=(pB+q)(rB+s)=prB^2+(ps+qr)B+qs=pr(B+\beta)+(ps+qr)B+qs=(pr+ps+qr)B+pr\beta+qs。递归计算 L_0=(p+q)(s+r),L_1=qs,L=L_0+L_1,R_0=pr,R_1={\color{red}R_0\beta},R=R_1+L_1，则答案为 LB+R=[LB+R]。时间复杂度 T(k)=3T(k-1)+O(3^k)=O(k3^k)。
关于本题
我们还需要证明一个性质：
定理 . 对于对四则运算封闭的 n=[2^{2^k}]，任意 x<n 有 x^n=x。
证明 . x=0 时显然。否则 y\to xy 是 n 到本身的双射，且 0 映射到 0。因此 \prod\limits_{y=1}^{[n-1]}y=\prod\limits_{y=1}^{[n-1]}xy，两边消去 \prod\limits_{y=1}^{[n-1]}y 可得 x^{[n-1]}=1，即 x^n=x。
以上。