Nimber系列略学习笔记
Nimber系列略学习笔记
前言
\(\text{Nim+Number=Nimber}\)
基于我们熟悉的博弈问题 \(\text{Nim}\) 问题，我们定义了多 \(\text{Nim}\) 问题的和，即 \(\text{Nim}\) 和
我们知道 \(\text{Nim}\) 和就是异或运算，为了构成一个更完整的 \(\text{Number}\) 域，又引入一种新的运算
即 \(\text{Nim}\) 积
定义
对于在 \([0,2^{2^m})\) 上的整数，定义两种 \(\text{Nim}\) 运算，构成一个封闭的域
- \(\text{Nim}\) 和 \(\oplus\)，\(\displaystyle x\oplus y=\text{mex}\{\{a\oplus y|a<x\}\cup\{x\oplus b|b<y\}\}\)
其中对于非负整数集合的 \(\text{mex}\) 运算即求不在集合中的最小非负整数
也就是 \(\text{Nim}\) 游戏的"和"
- \(\text{Nim}\) 积 \(\otimes\)
需要先介绍高维 \(\text{Nim}\) 游戏
对于一维情况：
数轴上整点处有若干黑点 \(x_i\)，每次操作可以选择一个黑点 \(x_i\)，找到 \(a<x_i\)。
将线段 \([a,x_i]\) 两端点的黑白翻转。
对于二维情况：
平面上整点处有若干黑点 \((x_i,y_i)\)，每次选择一个黑点 \((x_i,y_i)\)，找到另一个点 \((a,b),a<x_i,b<y_i\)。
将矩形 \((a,b)-(x_i,y_i)\) 四个顶点的颜色翻转。
对于三维情况：
空间上整点处有若干黑点 \((x_i,y_i,z_i)\)，每次选择一个黑点 \((x_i,y_i,z_i)\)，找到另一个点 \((a,b,c),a<x_i,b<y_i,c<z_i\)。
将长方体 \((a,b,c)-(x_i,y_i,z_i)\) 八个顶点的颜色翻转。
\(\vdots\)
\(\text{Nim}\) 积是高维 \(\text{Nim}\) 游戏的降维操作，显然各个维度之间无序，每个黑点之间可以通过 \(\text{Nim}\) 和相加。
由此定义在二维 \(\text{Nim}\) 游戏上的 \(\text{Nim}\) 积运算。
\(x\otimes y=\text{mex}\{(a\otimes y)\oplus (x\otimes b)\oplus(a\otimes b)|a<x,b<y\}\)
相较于 \(\text{Nim}\) 和，\(\text{Nim}\) 积运算十分复杂，需要若干性质简化运算
- 基础运算律
\(x\otimes 1=x\)
\(x\otimes y=y\otimes x\)
\((x\otimes y)\otimes z=x\otimes (y\otimes z)\)
\(2^{2^n}\otimes 2^{2^m}=\left\{\begin{aligned}2^{2^n+2^m} && n\ne m\\ 3\cdot 2^{2^n-1} && n=m\end{aligned}\right.\)
\(2^{2^n}\otimes x=2^{2^n}\times x\ (x<2^{2^n})\)
对于 \(x,y\in [0,2^{2^m})\)，利用性质3，用减半的方法优化运算，令 \(n=2^{m-1}\)
\(x=a\cdot 2^n+b,y=c\cdot 2^n+d,a,b,c,d\in[0,2^n)\)
\(x\otimes y=(a\otimes 2^n\oplus b)\otimes (c\otimes 2^n\oplus d)\)
\(=((a\otimes c)\otimes (3\cdot 2^{n-1}))\oplus (2^n\cdot ((a\otimes d)\oplus (b\otimes c))\ ) \oplus (b\otimes d)\)
\(=((a\otimes c)\otimes (2^{n}\oplus 2^{n-1}))\oplus (2^n\cdot ((a\otimes d)\oplus (b\otimes c))\ ) \oplus (b\otimes d)\)
\(=((a\otimes c)\otimes 2^{n-1})\oplus (2^n\cdot ((a\otimes c)\oplus (a\otimes d)\oplus (b\otimes c))\ ) \oplus (b\otimes d)\)
\(=((a\otimes c)\otimes 2^{n-1})\oplus (2^n\cdot ((a\oplus b)\otimes (c\oplus d)\oplus (b\otimes d))) \oplus (b\otimes d)\)
由此进行暴力递归需要依次计算 \(a\otimes c,(a\otimes c)\otimes 2^{n-1},b\otimes d,(a\oplus b)\otimes (c\oplus d)\)。
复杂度为 \(O(4^{m})\)，由于 \(2^{n-1}\)。
对于 \(2^{32}\) 以内的运算，即 \(m=5\)，看起来已经可以接受?
应用原根的优化
\(\text{Nimber}\) 域内是存在原根的，\([0,2^{16})\) 域内最小的原根是 \(258\)。
如果预处理出 \([0,2^{16})\) 以内所有数的原根指标和乘法表，即可 \(O(1)\) 查询 \([0,2^{16})\) 任意数的 \(\text{Nimber}\) 积。
由此也可以仅通过一次递归计算 \([0,2^{32})\) 域内的 \(\text{Nimber}\) 积。
更多运算
对于 \([0,2^{2^m})\) 域内的 \(\text{Nimber}\)，由性质 \(x^{2^m}=x\) 导出的运算有
\(\displaystyle \frac{1}{x}=x^{2^m-2}\)
\(\sqrt x=x^{2^{m-1}}\)