Nim积

参考资料：

• zjp-shadow 的博客
• chitanda 的博客
• suwakow 的博客

定义

定义 $x$ 和 $y$ 的 Nim 积为 $x\otimes y = \max\{(a\otimes b) \oplus (a\otimes y) \oplus (x\otimes b), 0\le a < x, 0\le b < y\}$

性质

运算性质

• $x\otimes 0 = 0\otimes x = 0$

• $x\otimes 1 = 1 \otimes x = x$

• $x\otimes y = y \otimes x$

• $(x\otimes y) \otimes z = x \otimes (y\otimes z)$

• $x\otimes (y\oplus z) = (x\otimes y) \oplus (x\otimes z)$

费马数

定义 Fermat 2-power 为 $2^{2^n}$，其中 $n\in \N$，设其为 $a$。有如下性质：

1. $a\otimes x = a\times x (x < a)$
2. $a\otimes a = \frac{3}{2} a$

计算

计算过程

设 $g(x,y) = 2^x \otimes 2^y$，$f(x,y) = x\otimes y$。

对于任意的 $x,y$，考虑将它用分配律（$x\otimes (y\oplus z) = (x\otimes y) \oplus (x\otimes z)$）拆开，转化成 $f(x,y) = \oplus_{x’\in x, y’\in y} g(x’,y’)$。

下面考虑怎么求 $g(x,y)$。

将 $x,y$ 的二进制位拆出来，转化成费马数相乘：

$$2^x \otimes 2^y = (\prod_{x'\in x} 2^{2^{x'}}) \otimes (\prod_{y\in y} 2^{2^{y'}} )= (\otimes_{x'\in x} 2^{2^{x'}}) \otimes (\otimes_{y\in y} 2^{2^{y'}} )$$

考虑 $x,y$ 的最高位，设为 $u$：

1. $u\in x, u\in y$：设 $M = 2^{2^u}, A = 2^{x-2^u}, B=2^{y-2^u}$，则 $g(x,y) = (\frac{3}{2} M) \otimes A\otimes B$。
2. $u\in x,u\notin y$：设 $M=2^{2^u}, A=2^{x-2^u}, B=2^y$，则 $g(x,y) = M \otimes A \otimes B$

$A\otimes B$ 的部分可以往下递归；我们把往下递归的部分展开，发现 $g(x,y)$ 正是：

$$(\otimes_{u\in (x \text{ xor } y)} 2^{2^u}) \otimes (\otimes_{u\in (x\text{ and } y)} \frac{3}{2} 2^{2^u})\\ = (\prod_{u\in (x \text{ xor } y)} 2^{2^u}) \otimes (\otimes_{u\in (x\text{ and } y)} \frac{3}{2} 2^{2^u})$$

对于后者，直接调用 $f(x,y)$ 递归计算即可。

复杂度分析

参考 2009 论文《从“k倍动态减法游戏”出发探究一类组合游戏问题》 p25（？）

据说是 $O(\log x \log y)$

习题

划愤 （高维 Nim 积行列式）

hdu3404 Switch lights（二维 Nim 积模板）