On nim multiplication and some related games

这篇blog要介绍的是有关nim multiplication（nim积）的概念以及一些应用。

在这篇blog中，我会用$\oplus$来表示nim和运算，用$\otimes$来表示nim积运算。

Turning Games

Turning Games,指的是一类这样的游戏: 有$n$枚硬币排成一排，其中每枚硬币可能正面向上也可能反面向上。两个人轮流操作，每次操作包括将一些$限定的$集合中的硬币翻面，但必须保证翻面的硬币的集合中最右边的一枚一开始一定是正面朝上的。当一个人无法操作时，他将输掉游戏。可以发现，在这样的定义下，Turning Games永远是impartial且finite的，所以可以使用Sprague-Grundy定理计算胜负态。对于这一类Turning Games,有一个十分好用的定理:

定理: Turning Games中某一个局面的$SG$值，等于局面中每个正面朝上的硬币单一存在时的局面的$SG$值的nim和（异或和）

这个定理并不难证明，我们可以考虑把翻面的操作当作加一个相同的copy，因为在nim和的定义下两个相同数的nim和是$0$，所以可以发现这两种方式是等价的，也就是说每个位置的$SG$值是独立的。

下面我们介绍一些经典的Turning Games的例子:

Turning Turtles

在这个例子中，每个人可以翻转一枚或者两枚硬币，但最右边一枚硬币一开始一定是正面朝上的。

对于这个游戏，每个位置的SG值应该是怎么样的呢? 实际上，对于从左往右第$x$枚硬币（$x$从$0$开始），它的$SG$值为$G(x)=x+1$,也就是说，我们可以把每个朝上的硬币看做一个Nim堆，堆的大小就是它的编号加一。

定理: 对于Turning Turtles游戏，$G(x)=x+1$

这个的证明可以通过考虑这个游戏和Nim​游戏的等价，并不难考虑。

Mocking Turtles

在这个例子中，每个人可以翻转一枚,两枚或者三枚硬币，但最右边一枚硬币一开始一定是正面朝上的。

这个问题不像前一个问题有那么显然的特征，于是我们可以先利用Sprague-Grundy定理打出前几项的表来观察:

通过打表我们可以看出$G(n)$总是$2n$或者$2n+1$,进一步观察发现$G(n)=\begin{cases} 2n & n\text{ is odious} \ 2n+1 & n\text{ is evil}\end{cases}$

其中odious表示二进制位中有奇数个$1$，evil表示二进制位中有偶数个$1$.

证明的话可以考虑通过Sprague-Grundy定理，$G(n)$是不是以下任何一种形式的最小的非负整数:

​ $0,G(a),G(a)\oplus G(b)$

然后利用数学归纳法进行证明。

Moebius, Mogul, Gold Moidores, and The Mock Turtle Theorem

对于上述两个游戏的综合，也就是每个人可以翻转$[1,t]$枚硬币，但最右边一枚硬币一开始一定是正面朝上的。

我们之前讨论了$t=2$和$t=3$的情况，实际上，只有$t=2m+1$的情况是有趣的$为什么?之后会说$。对于$t=3$的情况称作Mocking Turtles,$t=5$的情况称作Moebius,$t=7$的情况称作Mogul,$t=9$的情况称作Gold Moidores.对于$t>3$情况下的$G(n)$的计算没有直接的公式，但是下面的The Mock Turtle Theorem给出了$t=2m$和$t=2m+1$下$G(n)$的关系:

The Mock Turtle Theorem: 对于$t=2m+1$的情况，所有$G(n)$的二进制位中都包含奇数个$1$,且$t=2m$时的$G(n)$是$t=2n+1$时的$G(n)$值去掉最后一个二进制位的值（即除以二下取整）

对于这个定理的证明以及关于这些游戏的更多信息，可以参照由Elwyn R.Berlekamp,John H.Conway和Richard K.Guy写的Winning Ways For Your Mathematical Plays,Volume 3

Motley

这个例子中，每个人可以翻转任意枚硬币，但最右边一枚硬币一开始一定是正面朝上的。

很显然，这个游戏除非一开始就没有正面朝上的硬币，否则先手必胜。这个游戏的$SG$函数如下所示:

定理: 对于Motley游戏，$G(x)=2^x$

Twins,Triplets, Etc.

在Twins游戏中，每个人必须翻转恰好$2$枚硬币，但最右边一枚硬币一开始一定是正面朝上的。

在Triplet游戏中，每个人必须翻转恰好$3$枚硬币，但最右边一枚硬币一开始一定是正面朝上的。

很显然，Twins游戏的$SG$值就是Turning Turtles游戏前面加$1$个$0$，Triplets游戏的$SG$值就是Mocking Turtles游戏前面加$2$个$0$，依次类推。

Ruler

在这个例子中，每个人可以翻转任意枚连续的硬币，但最右边一枚硬币一开始一定是正面朝上的。

对于Ruler游戏，容易证明以下定理成立:

定理: 对于Ruler游戏，$G(x)=2^i$，其中$i$是满足$2^i \leq x+1$的最大的$i$

An example

这是一道来自Petrozavodsk Summer-2014. Warsaw U Contest的题，题面如下:

Jack和Chip在玩翻硬币游戏，规则是每个人可以翻转任意枚的硬币，但最右边一枚硬币一开始一定是正面朝上的，且翻转硬币的下标集合排序后构成等差数列。给定初始$n\leq 3000$枚硬币的正反情况，问先后手谁会获胜，若先手获胜，给出一个获胜的第一步操作。

这个题目，对于知道了翻硬币游戏中每个硬币的$SG$值独立就很简单了，可以通过$dp$在$O(n(\frac{n}{1}+\frac{n}{2}+\frac{n}{3}+\dots+\frac{n}{n})=n^2\log{n})$的时间里计算出所有位置的$SG$值，第一步操作同样枚举即可。

The 2-Dimensional Case

下面我会介绍一些二维的Turning Game, 其定义是在一个二维平面上翻硬币，其中每枚硬币可能正面向上也可能反面向上。两个人轮流操作，每次操作包括将一些$限定的$集合中的硬币翻面，但必须保证翻面的硬币的集合中最右下的一枚一开始一定是正面朝上的。当一个人无法操作时，他将输掉游戏。

很明显，二维Turning Game也具有之前介绍的$SG$值独立性，在这里我们把第$a$行第$b$列的硬币正面朝上的$SG$值记为$SG(a,b)$.

Acrostic Twins

这里是一个比较简单的例子。在这个例子中，每个人可以翻转同一行的两枚或者同一列的硬币，但最右下一枚硬币一开始一定是正面朝上的。我们直接给出计算$SG$值的方法,证明略去:

定理: 对于Acrostic Twins游戏，$G(a,b)=a\oplus b$

Turning Corners

这是一个更加有趣的例子，也正是在这个例子里我们得以引出nim multiplication的概念。在这个例子中，每个人可以翻转某一个矩形的四个角上的硬币，但最右下一枚硬币一开始一定是正面朝上的。

根据Sprague-Grundy定理，$G(a,b)=mex{G(a’,b),G(a,b’),G(a’,b’)}$,其中$a’$和$b’$是满足$0\leq a’<a,0\leq b’<b$的任意数字。在这里，我们先给出$a,b<16$的$SG$值的表（下标从$0$开始):

Nim Multiplication

可以观察到$G(0,n)=0$,$G(1,n)=1$，于是我们定义nimber意义下的乘法nim multiplication: $a\otimes b=G(a,b)$,我们把$a\otimes b$称作$a$和$b$的nim-product.

令人惊奇的是，nim-multiplication和nim-addition有着类似普通乘法和加法的结合律:

Nim Distributive law: $a\otimes (b\oplus c)=a \otimes b \oplus a \otimes c$

nim-multiplication本身还具有交换律和结合律:

Nim Multiplication Commutativity law: $a\otimes b=b \otimes a$

Nim Multiplication Associativity law: $a\otimes (b\otimes c)=(a\otimes b)\otimes c$

那么，应当如何计算$a\otimes b$呢?相较于nim addition,nim multiplication的计算要复杂很多，且nim multiplication的计算很大程度上要依靠对于Fermat powers of $2$的计算。对于nim multiplication有以下定理:

如果$N$是一个Fermat powers of $2$，即$N=2^{2^n}$,其中$n$是非负整数，那么有:

$N \otimes a = N\times a$, 其中$a<N$

$N\otimes N=\frac{3}{2}N$

如果$a,b<2^{2^n}$,那么$a\otimes b< 2^{2^n}$

因此，对于$a\otimes b$的计算，我们可以将$a$和$b$拆成一些$2$的次幂的nim和，利用分配律转为计算$a’\otimes b’$,其中$a’$和$b’$都是$2$的次幂，然后再把$a’$和$b’$拆成一些Fermat powers of $2$的nim乘积利用结合律计算即可。正常的实现情况下，如果$a,b<A$，那么计算$a\otimes b$的复杂度是$O((\log A)^2)$的。

附上我的nim multiplcation模板: NimMultiplication.cpp,实际实现时还可以打出一些小范围的表减少程序运算的常数。

The Tartan Theorem

那么，这个nim multiplcation的定义有什么用呢? 事实上，如果我们把两个一维的turning game $A$和$B$结合到一起，表示所选的行应该遵从turning game $A$中的规定，所选的列应该遵从turning game $B$中的规定，那么我们把这个游戏叫做一个tartan game,用$A\times B$表示。

对于tartan game,有着如下的定理:

The Tartan Theorem: 对于一个tartan game $A\times B$，每个位置的$SG$值可以这样计算:

$G_{A\times B}(a,b)=G_{A}(a)\otimes G_{B}(B)$

因此，对于之前的Turning Corners游戏，我们可以知道Turning Corners=Twins$\times$Twins

考虑如下的Rugs游戏: 每次我们可以翻转一个矩形的硬币，但最右下一枚硬币一开始一定是正面朝上的。我们可以发现Rugs=Ruler$\times$Ruler,因此通过Tartan Theorem来计算Rugs游戏的$SG$值。

实际上，Tartan定理对更高维的情况也适用，这时每个状态的$SG$值是一维情况下各个状态的$SG$值的nim multiplcation。

A Field is Born!

对于nim addition和nim multiplication，有一个十分简洁但强大的结论。

定理: 对于某个非负整数$n$, 以及$S={x\vert x\in N, x<2^{2^n} }$,$(S,\oplus,\otimes)$构成了一个特征为2的域。

在几天前的XX Open Cup, Grand Prix of Warsaw中就有一个需要这个定理的题目L.Lati@s,在了解一些博弈论基础以及对nim multiplication和The Tartan Theorem的情况下，题目可以转化为:

求一个$n\times n$的矩阵$A$在nim addition和nim multiplcation所定义的域下的permanent. 其中$1\leq n\leq 150$, $0\leq A_{i,j}<2^{64}$.

计算一般域下矩阵的permanent显然是NP-Hard的，但是这个域的characteristic是2，因此矩阵的permanent就等于它的行列式（例:求一个二部图的完美匹配数模二意义下的余数），高斯消元即可。这里还涉及到一些复杂度的优化，有兴趣的同学可以尝试一下。

Did you see the convex hull?

今天介绍的是13年比赛Petrozavodsk Summer-2013. Gennady Korotkevich Contest 1中通过人数最少的一个题目 Icy Roads of Nomel. 初看似乎是一个十分简单的题目，但庞大的数据范围却让人望而却步。在解决问题的过程中十分巧妙地用到了一些几何性质，最后的AC代码也是十分简短，但是思考过程不可谓不复杂。在我看来，这道题的巧妙程度相比于同样是利用几何性质的Google Code Jam World Finals 2015 C Pretty Good Proportion可谓是有过之而无不及:

对于一个$n\times m$的网格图，我们有$n+1$条横线以及$m+1$条竖线，以及$(n+1)(m+1)$个交叉点。Acesrc想要从网格图左上角的交叉点$(0,0)$，每次只能向下走一格或者向右走一格，最终走到右下角的交叉点$(n,m)$。 每条横线和竖线都有一个权值，其中从上至下第$i$条横线的权值是$a_i$，从左至右第$i$条竖线的权值是$b_i$.当Acesrc位于交叉点$(i,j)$的时候，他向右走一格所需要的代价是$a_i$，向下走一格的代价是$b_j$。试问Acesrc走到右下角所需花费的最小代价之和是多少? 其中数据范围满足$n,m\leq 5\cdot 10^5,1\leq a_i,b_i\leq 10^9$

首先$O(nm)$的动态规划显然是不可取的。为了察觉到题目中蕴含的性质，我们先从一些基本情况进行考虑. 假设我们现在想从$(i_1,j_1)$到达$(i_2,j_2)$，其中$i_1<i_2,j_1<j_2$,且只考虑以下两种走法: 先从$(i_1,j_1)$到$(i_1,j_2)$,再从$(i_1,j_2)$到$(i_2,j_2)$; 或是先从$(i_1,j_1)$到$(i_2,j_1)$,再从$(i_2,j_1)$到$(i_2,j_2)$。

对于第一种走法，我们所需的代价是$x=b_{j_1}(i_2-i_1)+a_{i_2}(j_2-j_1)$;对于第二种走法，所需的代价则是$y=a_{i_1}(j_2-j_1)+b_{j_2}(i_2-i_1)$. 为了比较大小，我们做差得到$\Delta=y-x=(b_{j_2}-b_{j_1})(i_2-i_1)-(a_{i_2}-a_{i_1})(j_2-j_1)=\Vert X\times Y\Vert$,

其中

$X=(i_2-i_1，a_{i_2}-a_{i_1}),Y=(j_2-j_1，b_{j_2}-b_{j_1})$

这里向量的叉积就神奇地出现了!顺着这样的思路，我们建立两个二维平面上的点集$S_{1}={(i,a_{i})\vert 0\leq i\leq n}$和$S_{2}={(i,b_{i})\vert 0\leq i\leq m}$.然后一个贪心方法是根据每次对于右下位置叉积是否大于零决定向右走一格还是向左走一格。 这样显然是不正确的，反例也很好构造。 然而，对于这个贪心方法进行一些改造，我们便可以得到正确解法，首先是下面的一个结论:

对于点集$S_1$和$S_2$，在最优解下，只有在下凸包上的点会被经过

这个结论的证明并不复杂，只要利用一些叉积的几何性质即可，在这里略去（才不是因为懒得画图）。这样，我们可以得到一个改进了的算法: 根据下一步的叉积的符号，选择在第一个点集的凸包上向右移动一步，或者在第二个点集的凸包上向右移动一步。对于这个改进了的贪心，竟然可以被证明是正确的!证明方法也不难，就留作读者思考吧（笑）。 至此，我们以$O(n+m)$的复杂度解决了这个问题。

AC代码链接: Petrozavodsk Summer-2013. Gennady Korotkevich Contest 1 I. Icy Roads of Nomel

Elegant Brute Force

今天在ZJU训练XIV Open Cup named after E.V. Pankratiev. GP of SPb的时候遇到了这样一个有趣的题目，看起来是一个十分简单的bitmask dp，但是数据范围却令人感到头疼:

Alice和Bob正在玩一个游戏。 给定$n$个字符串$s_1,s_2,\dots,s_n$. 双方轮流选择$26$个字母中的$1$个，且不能选择已经被选过的字母。当一个人选择完了一个字母后，如果只用所有选择过的字母可以组成某个字符串$s_i$,那么这个人输掉游戏。现在想问在双方决策都最优的情况下，是先手会赢还是后手会赢? 其中$\sum\limits_{i=1}^{n}\vert s_i\vert \leq 10^6$

很明显，这里的每个字符串都可以转化成一个bitmask，游戏的要求也变成了每次添加一位，使得不存在某个bitmask是当前bitmask的子集。

如果这里的字符集的大小只有$\vert \Sigma \vert=20$，这就是一个十分常规的简单题，首先利用高位前缀和或者SOS DP,可以在$O(\vert \Sigma \vert2^{\vert \Sigma\vert})$的时间内计算出所有不能到达的bitmask, 然后再用一个$O(\vert \Sigma \vert2^{\vert \Sigma\vert})$的dp即可计算出最终答案。然而这里的限制条件是$\vert \Sigma \vert=26$,这样的做法显然无法在时限内通过。然而，虽然这题涉及到bitmask，可明显无法使用std::bitset进行优化，那么应该如何处理呢?

考虑我们是否还有什么性质没有利用到，然而结论是……似乎没有。我们现在的复杂度是$O(26\cdot 2^{26})$，如果能够将那个$26$的常数消掉，似乎复杂度就是正确的。然而我们应该怎样消掉这么大的一个常数呢……?我们需要再发掘一些可用的信息。我们注意到，我们之前无论是在计算高位前缀和还是进行dp的时候，我们的数组都是一个bool值。而如果我们使用unsigned int的话，便可以在同样的时间复杂度内存储32倍的信息!

于是答案便呼之欲出了: 我们建一个大小为$2^{21}$的unsigned int的数组$a$，数组$a[mask]$内存储的信息表示前21位是$mask$的bitmask中后$5$位一共$2^5=32$种情况下有哪些bitmask的值是为$1$的。计算高位前缀和和dp的时候都要分块内和块间两种情况进行讨论，这样的时间复杂度是$O((2^5+31)\cdot2^{21})$，可以在时限内通过。通过预处理和硬编码一些bitmask，最终的程序可以做到非常短。

写这篇博文的时候突然想起来这个technique似乎在哪里见过……好像是寒武纪camp的dreamoon contest?这个technique和bitset压位以及Method of Four Russians都有点相似，但又有不同，可以说是一种非常优雅而又具有技巧性的暴力了w。