chitanda's blog

吃蛋挞的咸鱼博客

0%

从 nim 和到 nim 积

发表于 更新于 阅读次数： Valine：

nim 和

在三个经典博弈中，我们介绍了 \(\text{nim}\) 和，即异或和，一般用符号 \(\oplus\) 来表示这种操作。接下来，将介绍几种翻硬币游戏。以下内容大部分是我高中时从一篇博客中看到的，但好像找不到原博文了，放了个内容差不多的博客链接在下面，如果想了解更多可以看博客。

\(n\) 枚硬币排成一排，有的正面朝上，有的反面朝上，将其从左至右按 \(1\) 到 \(n\) 编号。A 和 B 轮流翻硬币，每次翻动时，所翻的编号最大的硬币必须是从正面翻到反面，除此之外，还必须满足某种约束条件。不能翻者输。

约束条件一

每次只能翻一个或者两个，不需要连续。

这其实本质上和尼姆游戏是一样的。设第 \(i\) 个硬币为正表示有一个物品数为 \(i\) 的堆，那么如果只翻一枚硬币，相当于将这堆物品一次取完。如果翻两枚硬币分别编号 \(i\) 和 \(j\) ，假设 \(i\lt j\) ，那么相当于在一堆物品数为 \(j\) 的堆中取 \(j-i\) 个物品，该堆还剩 \(i\) 个物品。当第 \(i\) 枚硬币本身为反面朝上时很容易理解，而当第 \(i\) 枚硬币本身为正面朝上时，只需这么理解：两个物品数相同的堆是可以完全抵消的，从 \(\text{SG}\) 函数出发它们异或和为 \(0\) ，从游戏本身出发，若一个人操作其中一堆物品，另一个人只需在另一堆上复读即可。

约束条件二（Ruler 游戏）

每次翻动连续的至少一个硬币。

由约束条件一以及 \(\text{SG}\) 定理可以知道，一个局面，若有 \(k\) 枚硬币正面朝上，可以看作 \(k\) 个游戏的和，每个游戏中分别只有单独一枚硬币朝上。因此，只需要计算出只有一个硬币朝上的局面的 \(sg\) 值即可，设只有第 \(i\) 枚硬币朝上时游戏的 \(sg\) 值为 \(sg(i)\) ，那么根据约束条件，有：

\[sg(i)=mex\{0,sg(i-1),sg(i-1)\oplus sg(i-2),\dots,sg(i-1)\oplus \dots \oplus sg(1)\}\]

打表后发现：

i 0 1 2 3 4 5 6 7 8
sg 0 1 2 1 4 1 2 1 8

有 \(sg(i)=\text{lowbit}(i)\) ，其中 \(\text{lowbit}\) 函数即二进制中最低位的 \(1\) 所代表的值。

这里只介绍这么多了，更多的约束条件可以看参考资料博客链接。

nim 积

上面介绍了翻硬币的一维版，接下来将介绍二维版，即硬币不再是排成一排，而是一个矩阵。

将一个矩阵分成 \(n\) 行 \(m\) 列，共计 \(n\times m\) 个单元格，每个单元格上有一枚或正或反的硬币，每行从上到下按 \(0\) 到 \(n-1\) 编号，每列从左到右按 \(0\) 到 \(m-1\) 编号，那么第 \(x\) 行第 \(y\) 列的坐标为 \((x,y)\) 。A 和 B 轮流翻硬币，并且翻的硬币中存在一枚最右下的硬币，其他硬币的横纵坐标都不超过它，这枚硬币必须从正面翻到反面。不能翻者输

约束条件一

每次翻转一个连通块。

同理，用 \(sg(x,y)\) 表示只有第 \(x\) 行 \(y\) 列的硬币朝上时的 \(sg\) 值 。

可以继续打表： \[ \begin{aligned} 1 && 2 && 1 && 4 && 1 \dots \\ 2 && 4 && 8 && 16 && 32 \dots \\ 1 && 8 && 16 && 32 && 64 \dots \\ 4 && 16 && 32 && 64 && 128 \dots \\ 1 && 32 && 64 && 128 && 256 \dots \\ \dots \end{aligned} \] 若 \(x=0\) 或 \(y=0\) ，相当于一个 Ruler 游戏，有 \(sg(x,y)=\text{lowbit}(x+y+1)\) ，否则 \(sg(x,y)=2^{x+y}\) 。

约束条件二

每次翻转一个子矩阵的四个角。

\[sg(x,y)=\text{mex}\{sg(x,b)\oplus sg(a,y)\oplus sg(a,b) | 0\le a\lt x,0\le b\lt y\}\]

将 \(sg\) 表打出来： \[ \begin{aligned} 0 && 0 && 0 && 0 && 0 && 0 \dots \\ 0 && 1 && 2 && 3 && 4 && 5 \dots \\ 0 && 2 && 3 && 1 && 8 && 10 \dots \\ 0 && 3 && 1 && 2 && 12 && 15 \dots \\ 0 && 4 && 8 && 12 && 6 && 2 \dots \\ 0 && 5 && 10 && 15 && 2 && 7 \dots \\ 0 && 6 && 11 && 13&& 14 && 8 \dots \\ \dots \end{aligned} \] 此时似乎不再有规律了，找规律大法大失败。

但是，既然有游戏的“和”，那么有游戏的“积”也是很正常的，我们可以将这个游戏看成是两个一样的游戏相乘，这个游戏即一维版的翻硬币，不过编号变成了从 \(0\) 到 \(n-1\) ，每次必须翻恰好两个硬币，且编号大的那个必须是正面朝上（事实上，假如你忽略编号为 0 的硬币，这就和一维版本的约束条件一是一样的了）。

那么如何计算两个游戏相乘时的 \(sg\) 值呢，这里就必须引入 \(\text{nim}\) 积了。

形式化的，定义 \(n\) 个游戏 \(G_1,G_2,\dots ,G_n\) 的积 \(G(V,E)=G_1\times G_2\times \dots \times G_n\) 为：

  1. \(V=V_1\times V_2\times \dots \times V_n\) ，这里的 \(\times\) 代表的是笛卡尔积。
  2. \(E=\{(x,y)|(x_i,y_i)\in E_i,x=(x_1,x_2,\dots,x_n),y=\sum_{y_i^\ast\in\{x_i,y_i\}}(y_1^\ast,y_2^\ast,\dots,y_n^\ast)\}\) ，这里的 \(y\) 其实代表的是游戏的和，但是要除去 \(x\) 所代表的游戏本身，即相当于 \(2^n-1\) 个游戏的和。如果你觉得难以理解，那么举个不太严谨的例子，此题的一个坐标为 \((x_1,x_2)\) 的硬币，其能转移到的状态，即为 \((x_1,y_2),(y_1,x_2),(y_1,y_2)\) 这 \(3\) 个的和，其中 \(y_1\lt x_1\) ，\(y_2\lt x_2\) 。

tartan 定理：如果 \(sg_1(x)\) 是游戏 \(G_1\) 的 \(\text{SG}\) 函数，\(sg_2(x)\) 是游戏 \(G_2\) 的 \(\text{SG}\) 函数，那么游戏 \(G_1\times G_2\) 的 \(\text{SG}\) 函数 \(sg(x,y)=sg_1(x)\otimes sg_2(y)\) 。其中 \(\otimes\) 表示 \(\text{nim}\) 积。当然，这同样也可以拓展到多维游戏相乘的情况。

运算性质

和普通加法乘法类似，\(\text{nim}\) 和和积也满足一些性质：

  • 零值：\(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 \mathbb{N})\) 的数，我们称之为 Fermat 2-power 数，设一个 Fermat 2-power 数为 \(F=2^{2^a}\) ，那么有：

  • \(F\otimes x=F\times x\) ，其中 \(x<F\) 。
  • \(F\otimes F=\frac{3}{2}F=3\times 2^{2^a-1}\) 。
  • \(x\otimes y<F\) ，其中 \(x,y\lt F\) 。

计算方法

对于 \(x\otimes y\) ，考虑将他们二进制拆解，例如 \(3\otimes 5=(1\oplus 2)\otimes(1\oplus 4)=1\otimes 1+1\otimes 4+2\otimes 1+2\otimes 4\) ，这样我们就只需要考虑计算形如 \(2^x\otimes 2^y\) 这样的 \(\text{nim}\) 积。在实际写代码的时候，可以预处理或者记忆化以供简化复杂度。

计算 \(2^x\otimes 2^y\) ，再将 \(x\) 和 \(y\) 二进制分解，变成 Fermat 2-power 数的情况，设 \(X,Y\) 分别代表二进制分解后 \(x,y\) 哪些位为 \(1\) 的集合，那么有 \(2^x\otimes 2^y=(\bigotimes_{x'\in X}2^{2^{x'}})\otimes (\bigotimes_{y'\in Y}2^{2^{y'}})\)，从高到低枚举二进制下每一位，设这一位为 \(2^a\) ，令 \(M=2^{2^a}\)： 1. 如果 \(x\) 和 \(y\) 这一位都是 \(1\) ，令 \(X=2^{x-2^a},Y=2^{y-2^a}\) ，那么 \(ans=(M\otimes X)\otimes(M\otimes Y)=(M\otimes M)\otimes (X\otimes Y)=\frac{3}{2}M\otimes (X\otimes Y)\) 。设这样的位的集合为 \(S_1\) 。 2. 如果 \(x\) 和 \(y\) 只有一个这一位为 \(1\) ，假设为 \(x\)，令 \(X=2^{x-2^a},Y=2^y\) ，答案为 \(ans=(M\otimes X)\otimes Y\) ，即 \(ans=M\otimes (X\otimes Y)\) 。设这样的位的集合是 \(S_2\) 。

最后，实际上： \[2^x\otimes 2^y=(\bigotimes_{i\in S_1}\frac{3}{2}2^{2^i})\otimes(\bigotimes_{i\in S_2}2^{2^i})=(\bigotimes_{i\in S_1}3\times 2^{2^i-1})\otimes(\prod_{i\in S_2}2^{2^i})\]

用 C++ 实现如下： 

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
int nim_mult(int x, int y);

static int f[32][32]; // must be initialized to -1
int nim_mult_2power(int x, int y){
	if (!x || !y) return 1 << (x + y);
	int &F = f[x][y];
	if (F != -1) return F;
	int ret = 1, tmp = 1;
	for(int i = 0; i < 6; ++i)
		if ((x ^ y) >> i & 1) tmp *= 1 << (1 << i);
		else if (x >> i & 1) ret = nim_mult(ret, 3 * (1 << ((1 << i) - 1)));
	return F = nim_mult(ret, tmp);
}

int nim_mult(int x, int y){
	if (x < 2 || y < 2) return x * y;
	int ret = 0;
	for(int i = 0; i < 32; ++i)
		if (x >> i & 1)
			for(int j = 0; j < 32; ++j)
				if (y >> j & 1)
					ret ^= nim_mult_2power(i, j);
	return ret;
}

后来面包哥哥 @tangjz 教了我另一种做法，复杂度更低：

计算 \(x\otimes y\) ，假设有 \(x\ge y\) ，设 \(2^{2^a}\le x\lt 2^{2^{a+1}}\) ，令 \(M=2^{2^a}\) ，则 \(x=pM+q , y=sM+t(0\le q,t\lt M)\) 。那么有： \[ \begin{aligned} x\otimes y&=(pM+q)\otimes(sM+t)\\ &=(pM\oplus q)\otimes(sM\oplus t)\\ &=(p\otimes M\otimes s\otimes M)\oplus(p\otimes M\otimes t)\oplus(s\otimes M\otimes q)\oplus(q\otimes t) \\ &=(\frac{3}{2}M\otimes p\otimes s)\oplus (M\otimes(p\otimes t\oplus s\otimes q))\oplus(q\otimes t)\\ &=((M\oplus \frac{M}{2})\otimes p\otimes s))\oplus (M\otimes(p\otimes t\oplus s\otimes q))\oplus(q\otimes t)\\ &=M\times (p\otimes s\oplus p\otimes t\oplus s\otimes q)\oplus(q\otimes t)\oplus(\frac{M}{2}\otimes p\otimes s)\\ &=M\times ((p\oplus q)\otimes(s\oplus t)\oplus (q\otimes t))\oplus(q\otimes t)\oplus(\frac{M}{2}\otimes p\otimes s) \end{aligned} \] 令 \(t_0=q\otimes t,t_1=(p\oplus q)\otimes (s\oplus t),t_2=p\otimes s\otimes \frac{M}{2}\) ，则： \[x\otimes y=M\times(t_0\oplus t1)\oplus t_0\oplus t_2\]

其中，计算 \(\frac{M}{2}\otimes v\) 复杂度为 \(O(3^{d-1})\) ，因此总复杂度为 \(O(d\times 3^{d})\) ，其中 \(d\) 为递归层数，约为 \(\log_2\log_2 x\)。同时，可以记忆化 \(x\) 和 \(y\) 都比较小的情况。

此外，\(\text{nim}\) 积也存在逆元。

约束条件三（Rugs 游戏）

每次翻转一个子矩阵。

即两个 Ruler 游戏相乘，那么 \(sg(x,y)=\text{lowbit}(x+1)\otimes \text{lowbit}(y+1)\) 。

最后，建议做一做 PE459 来练习一下 \(\text{nim}\) 积。

参考资料