题解 P2594 【[ZJOI2009]染色游戏】
BinDir0
·
·
题解
也可以在我的博客查看owo
做法另外一篇题解已经说得很清楚了，但似乎没有对于本题 SG 函数正确性的证明，我来口胡一下（
证明：
猜想：
\operatorname{SG}(i,j)=\begin{cases}\operatorname{lowbit}(i+j-1),i=1\lor j=1\\2^{i+j-2},otherwise\end{cases}
我们要用到一个结论： 局面的 SG 值等于局面中所有反面朝上的硬币单独存在时的 SG 值的异或和 。然而这个结论我不太会证（）。我们暂且使用它而不证明。
首先当 i=1\lor j=1 成立时，本题相当于一维放硬币问题，其 SG 函数等同于一维的 lowbit(i)。因为 i 或 j 中至少有一个是 1，于是我们只需要将横纵坐标相加再 -1 即可消去为 1 的那一维。
对于其他情况我们使用数学归纳法：
首先对于 \operatorname{SG}(2,2) ，有以下几种选择方案（下图中 0/1 代表反转后分别是正面/反面朝上）：
\begin{matrix} 0&0\\0&0 \end{matrix} ,\operatorname{SG}=0
\begin{matrix} 0&1\\0&0 \end{matrix} ,\operatorname{SG}=\operatorname{SG}(1,2)=2
\begin{matrix} 0&0\\1&0 \end{matrix} ,\operatorname{SG}=\operatorname{SG}(2,1)=2
\begin{matrix} 0&1\\1&0 \end{matrix} ,\operatorname{SG}=\operatorname{SG}(1,2)\space\operatorname{xor}\space \operatorname{SG}(2,1)=0
\begin{matrix} 1&1\\0&0 \end{matrix} ,\operatorname{SG}=\operatorname{SG}(1,1)\space\operatorname{xor}\space \operatorname{SG}(1,2)=3
\begin{matrix} 1&0\\1&0 \end{matrix} ,\operatorname{SG}=\operatorname{SG}(1,1)\space\operatorname{xor}\space \operatorname{SG}(2,1)=3
\begin{matrix} 1&1\\1&0 \end{matrix} ,\operatorname{SG}=\operatorname{SG}(1,1)\space\operatorname{xor}\space SG(1,2)\space\operatorname{xor}\space \operatorname{SG}(2,1)=1
还有一种特殊情况就是 $i=2\land j>2$ 或 $i>2\land j=2$，不难发现它们是等价的，因此这里我们只以 $i=2\land j>2$ 为例。此时有 $\operatorname{SG}(i,j-1)=2^{i+j-3},\operatorname{SG}(i-1,j)=\operatorname{lowbit}(j)$。由 SG 函数定义有对于左上角为 $(1,1)$，右下角为 $(i,j-1)$ 的不包含右下角的矩形，在其中选择满足题目要求的连通块所得 SG 函数值域取遍 $[0,2^{i+j-3}-1]$。因此在选择 $(i,j-1)$ 一点与上述矩形范围内取连通块可以取遍 $2^{i+j-3}\space\operatorname{xor}\space[0,2^{i+j-3}-1]$ 即 $[2^{i+j-3},2^{i+j-2}-1]$ 范围内的值；可以证明在 $j\ge3$ 时有 $\operatorname{SG}(i-1,j)=\operatorname{lowbit}(j)\le 2^{i+j-4}$ （在 $j=3$ 时有 $\operatorname{lowbit}(3)=1\le 2^{i+j-4}$ ，而在 $j>3$ 时有 $\operatorname{lowbit}(j)\le j \le 2^{j-2}=2^{i+j-4}$），因此在选择 $(i-1,j)$ 一点与上述矩形范围内取连通块可以取遍 $\operatorname{lowbit}(j)\space\operatorname{xor}\space[0,2^{i+j-3}-1]$ 也即 $[0,2^{i+j-3}-1]$ 范围内的值（因为 $\operatorname{lowbit}(j)$ 一位上为 1 的数异或后该位会变成 0，为 0 的数该位会变为 1，值域仍取遍）。做一下 mex 可得 $\operatorname{SG}(i,j)=2^{i+j-2}$，符合猜想。
对于 $i>2\land j>2$ 的 $(i,j)$，由数学归纳法有 $\operatorname{SG}(i,j-1)=\operatorname{SG}(i-1,j)=2^{i+j-3}$，由 SG 函数定义有对于左上角为 $(1,1)$，右下角为 $(i,j-1)$ 的不包含右下角的矩形，在其中选择满足题目要求的连通块所得 SG 函数值域取遍 $[0,2^{i+j-3}-1]$。因此除选择点 $(i,j)$外，在 $(i,j-1),(i-1,j)$ 两点与上述矩形范围内取连通块可以取遍 $[0,2^{i+j-3}-1]$ 范围内的值，在 $(i,j-1)$ 一点与上述矩形范围内取连通块可以取遍 $2^{i+j-3}\space\operatorname{xor}\space[0,2^{i+j-3}-1]$ 即 $[2^{i+j-3},2^{i+j-2}-1]$ 范围内的值，做一下 mex 可得 $\operatorname{SG}(i,j)=2^{i+j-2}$，符合猜想。
证毕。
顺便挂一下代码：
```cpp
#include <bits/stdc++.h>
using namespace std;
int T , n , m , sg[110][110] , init() , f[220] , flag;
string s;
inline void init()
{
for(int i = 1 ; i <= 100 ; i++ ) sg[i][1] = sg[1][i] = log2(i & (-i));
for(int i = 2 ; i <= 100 ; i++ )
for(int j = 2 ; j <= 100 ; j++ ) sg[i][j] = i + j - 2;
return ;
}
int main()
{
init();
scanf("%d" , &T);
while(T--)
{
memset(f , 0 , sizeof(f)); flag = 0;
scanf("%d%d" , &n , &m);
for(int i = 1 ; i <= n ; i++ )
{
cin >> s;
for(int j = 1 ; j <= m ; j++ )
{
if(s[j - 1] == 'T') f[sg[i][j]] ^= 1;
}
}
for(int i = 0 ; i <= 200 ; i++ )
{
if(f[i])
{
flag = 1;
break;
}
}
if(flag) printf("-_-\n");
else printf("=_=\n");
}
return 0;
}
/*
1
3 4
TTHH
THTH
TTHH
*/
```