定义
定义作用在两个非负整数 (a, b) 上的运算 (otimes) 为 (aotimes b=operatorname{mex}_{0leq i< a, 0leq j<b}{(aotimes j)oplus (iotimes b)oplus (iotimes j) })，其中 (oplus) 为按位异或操作，也称为 Nim和，(otimes) 即为 Nim积。
基本性质
与整数的乘法和加法类似，Nim积 和 Nim和 满足交换律，结合律和分配律，即：
- (aotimes b=botimes a)
- ((aotimes b)otimes c=aotimes (botimes c))
- ((aoplus b)otimes c=aotimes coplus botimes c)
同时，(0) 和 (1) 分别是 Nim积 的零元和单位元，即：
- (0otimes a=aotimes 0=0)
- (1otimes a=aotimes 1=a)
由于 Nim积 与整数乘法如此高的相似性，许多由整数乘法和加法实现的算法，均可以用 Nim积 和 Nim和 来代替整数乘法和加法，如高斯消元等。
计算方式
经过数学家们的努力，人们得到了 Nim积 的两条重要规律：
- 设 (k) 为满足 (2^{2^k}> a) 的非负整数，则 (aotimes 2^{2^{k}}=acdot 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)，返回 (acdot b)。
- 若 (max(a, b)< 2^8)，且曾经计算过 (aotimes 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)），则：
[egin{aligned}aotimes b&= a_0otimes b_0oplus 2^{2^{k-1}}otimes (a_{1}otimes b_{0}oplus a_0otimes b_1)oplus (2^{2^{k-1}}oplus2^{2^{k-1}-1})otimes a_1otimes b_1\&=a_0otimes b_0oplus 2^{2^{k-1}}cdot ((a_0oplus a_1)otimes (b_0oplus b_1)oplus a_0otimes b_0)oplus 2^{2^{k-1}-1}otimes a_1otimes b_1end{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 mod 2^{2^k})
具体证明较为繁琐，珂以类比整数乘法运算中的费马小定理理解。