前言

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

本学习笔记基本参考【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}$ 了,意义好像不是很大,所以不管了。

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