【学习笔记】Nim积

定义

定义作用在两个非负整数 \(a, b\) 上的运算 \(\otimes\) 为 \(a\otimes b=\operatorname{mex}_{0\leq i< a, 0\leq j

基本性质

与整数的乘法和加法类似，Nim积 和 Nim和 满足交换律，结合律和分配律，即：

\(a\otimes b=b\otimes a\)

\((a\otimes b)\otimes c=a\otimes (b\otimes c)\)

\((a\oplus b)\otimes c=a\otimes c\oplus b\otimes c\)

同时，\(0\) 和 \(1\) 分别是 Nim积 的零元和单位元，即：

\(0\otimes a=a\otimes 0=0\)

\(1\otimes a=a\otimes 1=a\)

由于 Nim积 与整数乘法如此高的相似性，许多由整数乘法和加法实现的算法，均可以用 Nim积 和 Nim和 来代替整数乘法和加法，如高斯消元等。

计算方式

经过数学家们的努力，人们得到了 Nim积 的两条重要规律：

设 \(k\) 为满足 \(2^{2^k}> a\) 的非负整数，则 \(a\otimes 2^{2^{k}}=a\cdot 2^{2^{k}}\)

\(2^{2^{k}}\otimes 2^{2^{k}}=\frac{3}{2}\cdot 2^{2^{k}}\)

其中形如 \(2^{2^k}\) 的数被称为费马数。

有了这两条规律，结合上述的基本性质，我们可以得到一个单次 \(O(\log^2 n)\) 复杂度的分治算法：

若 \(\min(a, b)\leq 1\)，返回 \(a\cdot b\)。

若 \(\max(a, b)< 2^8\)，且曾经计算过 \(a\otimes b\)，则返回记忆的值。（很强的常数优化）

否则设 \(k\) 为满足 \(2^{2^k}>\max(a, b)\) 的最小非负整数，\(a_0, b_0\) 为 \(a, b\) 较低的 \(2^{2^{k-1}}\) 位，\(a_{1}, b_{1}\) 为 \(a, b\) 较高的 \(2^{2^{k-1}}\) 位（即 \(2^{2^{k-1}}>a_0, b_0, a_1, b_1\)），则：

\[\begin{aligned}a\otimes b&= a_0\otimes b_0\oplus 2^{2^{k-1}}\otimes (a_{1}\otimes b_{0}\oplus a_0\otimes b_1)\oplus (2^{2^{k-1}}\oplus2^{2^{k-1}-1})\otimes a_1\otimes b_1\\&=a_0\otimes b_0\oplus 2^{2^{k-1}}\cdot ((a_0\oplus a_1)\otimes (b_0\oplus b_1)\oplus a_0\otimes b_0)\oplus 2^{2^{k-1}-1}\otimes a_1\otimes b_1\end{aligned}

\]

实现代码如下：

ull nimProd(ull x, ull y, int p = 32) {

if (x <= 1 || y <= 1) return x * y;

if (p < 8 && rem[x][y]) return rem[x][y];

ull a = x >> p, b = ((1ull << p) - 1) & x, c = y >> p, d = ((1ull << p) - 1) & y;

ull bd = nimProd(b, d, p >> 1), ac = nimProd(nimProd(a, c, p >> 1), 1ull << p >> 1, p >> 1), ans;

ans = ((nimProd(a ^ b, c ^ d, p >> 1) ^ bd) << p) ^ ac ^ bd;

if (p < 8) rem[x][y] = rem[y][x] = ans;

return ans;

}

Nim积 的另一个重要性质为：\(a^{2^{2^k}-1}\equiv 1 \bmod 2^{2^k}\)

具体证明较为繁琐，珂以类比整数乘法运算中的费马小定理理解。

例题：[SOJ]【WC 联训 Round #6】愤划