「CF1451F」Nullify The Matrix

Aleph-0

题目链接

Description

给定一个网格，每个格子上有一个非负的值 $a[r1][c1]$，两个人在上面玩游戏。

每个玩家按照如下顺序操作：

• 选择两个点 $(r1, c1)$ ，$(r2, c2)$ ，满足 $r2 \le r1, c2 \le c1$ ，并且 $a[r1][c1]$ 不为 0
• 将 $a[r1][c1]$ 的值减去一个正数，
• 选出 $(r1,c1)$ 到 $(r2,c2)$ 的一条最短路，将路径上的每个点（包括终点但是不包括起点），将路径上的每一个点改成任意玩家想要的值
• 经过操作后满足网格中的所有值非负

不能操作的人输，问先手是否必胜。

Solution

官方题解给出了一个结论，我们计算出每条满足 $r + c$ 为定值 $d$ 的对角线上所有值的异或和 $xor_d$，如果有

$$\forall d, xor_d = 0$$

那么先手必败，否则先手必胜。

证明也比较简单，我们设状态 $S$ 和 $S’$ ：

$$S : \forall d, xor_d = 0\\ S' : \exist d,xor_d \ne 0\\$$

1. 对于必败态，也就是网格全 0，状态显然为 $S$
2. 对于任意状态 $S$ ，经过一次操作后必然会变成 $S’$，考虑起点所在的对角线的异或和，必然会不为 0
3. 对于任意状态 $S’$ ，存在一种操作满足操作后状态回到 $S$ ，令起点为最大的 $d$ 满足 $xor_d \ne 0$ ，在这一条对角线上选一个非 0 数作为起点，终点设为 $(1,1)$ ，易证总能把每个对角线都变成 0

看起来很好理解，但是要是没有想到这个结论的话，想起来有些难度。这里提供另一种理解方式

Solution2

首先观察这个模型，容易发现他是一个翻硬币的模型，而对于翻硬币的博弈模型存在一个结论，一个局面的 $sg$ 值等于棋盘上每个棋子单独存在时的 $sg$ 值的异或和，换而言之，我们可以把棋盘上的每个棋子看做是一个独立的游戏，算出每个游戏的 $sg$ 然后合并（也就是异或起来）。

现在问题来了，对于这个游戏，只有一个棋子的 $sg$ 是多少。首先考虑计算假设只有 $(1,1)$ 有值，显然 sg 值为棋子个数，现在考虑 $(x,y)$ 满足 $x + y = 3$ 的格子上有值的sg值是多少（也就是第一条对角线），但是你发现这个东西没法算，因为他的后记状态太多了，你可以在拿掉这个格子上的棋子后在 $(1, 1)$ 上放上无数颗棋子，也就是说sg值是 $\aleph$ ，然后就完蛋了，因为无穷之间的异或是啥我们根本就不知道。

我们可以换一个想法，把无穷看做是 x ，于是我们要算的 sg​ 值便是一个多项式了，因为不同阶的无穷我们根本就不知道怎么合并，所以我们直接不合并，只和并同类项，于是我们可以得到一个格子 $(i,j)$ 的 sg值为 $a[i][j]\cdot\aleph^{i+j-2}$ ，然后我们把所有格子的sg值合并起来，最终的sg值为0当且仅当每一项前的系数都是 0，于是形式化的写出来，就和上面的那个式子一样了。