【学习笔记】Nimber

前言

群除我会 欸好像不是，反正看着也就图一乐。

本学习笔记基本参考【IOI2020 论文集】罗煜翔，浅谈 Nimber 和多项式算法
还有这篇文章

由于本人水平巨大十分超级有限，所以只看了关于 $\text{nim}$ 和与 $\text{nim}$ 积相关的内容。后面的都鸽了。

定义

定义 $\text{Nimber} *n$ 为单堆石子的 $\text{Nim}$ 游戏。其中 $\text{Nim}$ 游戏为：有一堆石子，共 $n$ 个，每次当前操作的人可以选择拿走正整数颗石子，不能操作者输。

$\text{Nimber}$ 可以这样归纳定义：

$$ *0=\{\varnothing\} $$

也就是 $0$ 个石子没法操作，直接输了。

$$ *(n+1)=*n \cup\{*n\}(n\ge 0) $$

即 $n+1$ 颗石子的后继状态，可以是 $n$ 颗石子的后继状态，或者 $n$ 颗石子的状态。对于两个游戏 $A,B$，可以定义他们的和：

$$ A\oplus B=\{a\oplus B|a\in A\}\cup\{A\oplus b|b\in B\} $$

也就是每次可以选择把其中一个游戏变成后继状态。显然有交换律和结合律。

两个游戏 $A,B$ 等价，当且仅当对于任何游戏 $C$，$A\oplus C$ 和 $B\oplus C$ 的胜负情况相同。

很多时候直接省略 $\text{Nimber}$ 前面的 $*$，而且有时候会直接对 $\text{Nimber}$ 的数值做运算。

$\text{Sprague-Grundy}$ 定理

$\text{Sprague-Grundy}$ 定理指出，任何一个 $\text{ICG}$ 都与一个 $\text{Nimber}$ 等价。同时，定义一个游戏的 $\text{SG}$ 函数为与该游戏等价的 $\text{Nimber}$。有广为人知的计算方法：

$$ \text{SG}(A)=\text{mex}\{\text{SG}(B)|A\rightarrow B\} $$

实际上就是把一个游戏变成了取石子。使用 $\text{mex}$ 的目的就在于，保证所有 $\text{SG}$ 小于当前值的局面都能到达。

对于一个 $B$ 满足 $A\rightarrow B$，如果 $\text{SG}(B)<\text{SG}(A)$，那就和 $\text{Nim}$ 一样，但是若 $\text{SG}(B)>\text{SG}(A)$，则操作到状态 $B$ 后，后手可以把状态变为一个状态 $C$ 使得 $\text{SG}(C)=\text{SG}(A)$。因为局面有限，所以一定会有一个时刻走 $\text{SG}(B)<\text{SG}(A)$ 的 $B$。

还有一个广为人知的结论：

$$ \text{SG}(A+B)=\text{SG}(A) \text{ xor } \text{SG}(B) $$

这个就可以通过 $\text{Nim}$ 的结论推出了。

$\text{Nim}$ 积

定义 $x,y$ 的 $\text{Nim}$ 积表示为 $x\otimes y$，计算方式为：

$$ x\otimes y = \text{mex}\{(a\otimes b) \oplus (a\otimes y) \oplus (x\otimes b)|0\le a<x,0\le b<y\} $$

他满足交换律，结合律，对 $\text{Nim}$ 和有分配律 看起来没啥人证了所以我也不会！。还有一些比较显然的，比如 $x\otimes 0=0,x\otimes 1=x$，也可以根据下面的组合意义来理解一下。

这个东西有一个如下的组合意义：

现在在平面直角坐标系上，点 $(x,y)$ 为黑色，其他整点均为白色。双方每次可以选择一个黑色点 $(p,q)$，并选择一个以 $(p,q)$ 为右上角的，面积 $>0$ 的矩形，将矩形的四个顶点的颜色翻转。
不能操作者输，问胜负情况。

这样看起来上面那个式子说的很对啊

考虑如何计算这个东西。接下来会不加证明地给出一车结论 主要是论文里也没讲！。

首先，在 $[0,2^{2^m})$ 以内的 $\text{Nimber}$ 构成一个有限域，对于形如 $2^{2^m}$ 的数，他们的 $\text{Nim}$ 积有如下性质：

若 $n\ne m$，则 $2^{2^n}\otimes 2^{2^m}=2^{2^n}\times 2^{2^m}$。

若 $n=m$，则 $2^{2^n}\otimes 2^{2^m}=\dfrac{3}{2}2^{2^n}=2^{2^n}\oplus 2^{2^n-1}$。

根据上面的结论，我们可以得到对于任意 $a\in[0,2^{2^m})$，有 $a\otimes 2^{2^m}=a\times 2^{2^m}$，因为 $\text{Nim}$ 积对 $\text{Nim}$ 和有分配律。

考虑一个类似分块的思想来计算 $x\otimes y$，设 $n=2^{m-1}$，$x=a\times 2^n+b,y=c\times 2^n+d$，其中 $0\le a,b,c,d< 2^n$，也就是把 $x,y$ 分为前后两半。

由于 $2^n$ 也是形如 $2^{2^m}$ 的数且 $a,c<2^n$，所以 $a\times 2^n=a\otimes 2^n$，$c$ 同理。且 $2^n\times a$ 的后面 $n$ 位都是 $0$，所以 $a\times 2^n+b=a\otimes 2^n\oplus b$。因此有：

$$ x\otimes y=(a\otimes 2^n\oplus b)\otimes(c\otimes 2^n\oplus d) $$

$$ =a\otimes c\otimes (2^n\oplus 2^{n-1})\oplus (a\otimes d\oplus b\otimes c)\otimes 2^n\oplus b\otimes d $$

$$ =a\otimes c\otimes 2^{n-1}\oplus (a\otimes d\oplus b\otimes c\oplus a\otimes c)\otimes 2^n\oplus b\otimes d $$

注意到 $(a\otimes d\oplus b\otimes c\oplus a\otimes c)=(a\oplus b)\otimes (c\oplus d)\oplus b\otimes d$，所以这样就只需要计算：

$$ (a\oplus b)\otimes (c\oplus d),a\otimes c,a\otimes c\otimes 2^{n-1},b\otimes d $$

直接递归 $m-1$ 的计算，复杂度是 $\mathcal{O}(4^m)$。但是实际上，由于需要计算 $a\otimes c\otimes 2^{n-1}$，$2^{n-1}$ 后半段一定是 $0$，所以实际上每次只需要往 $3$ 个里面递归，复杂度是：

$$ T(m)=3T(m-1)+\mathcal{O}(3^m)=\mathcal{O}(m3^m) $$

代码大概这样写：

int nim_Prod(int x, int y, int m) {
    if(!x || !y) return 0;
    if(m == 0) return 1;
    int n = p2[m - 1], a, b, c, d, ac, bd;
    a = x / p2[n], b = x % p2[n], c = y / p2[n], d = y % p2[n];
    ac = nim_Prod(a, c, m - 1), bd = nim_Prod(b, d, m - 1);
    return (nim_Prod((a ^ b), (c ^ d), m - 1) ^ bd) * p2[n] + (nim_Prod(p2[n - 1], ac, m - 1) ^ bd);
}

实际上加上了 if(!x || !y) return 0; 这句，复杂度直接从 $\mathcal{O}(4^m)$ 降到 $\mathcal{O}(m3^m)$，十分奇妙。

但这还是有点慢，考虑继续优化。意识到这是个有限域，计算加法是容易的，但计算乘法较为困难。这启示我们把 $\text{Nim}$ 积变为加法——求对数、指数。

也就是可以考虑找到原根，于是如果打表出所有数在 $\text{Nim}$ 积下的对数、指数，那操作就可以做到 $\mathcal{O}(1)$ 了！实际上，这个域真的有原根，对于 $m=4$ 的情况下，一个原根是 $258$。

但是对于 $m=5$，数字达到了 $2^{32}-1$，这不能打表。但是按照上面的 $\text{Nim}$ 积做法，递归一次就可以查表了，所以也可以认为是 $\mathcal{O}(1)$。再大就要用 $\text{unsigned long long}$ 了，意义好像不是很大，所以不管了。

好的我看懂的部分就到此结束了