自动搬运

查看原文

来自洛谷，原作者为

	BinDir0 AFO

搬运于2025-08-24 21:39:26，当前版本为作者最后更新于2020-09-17 21:42:46，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

也可以在我的博客查看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$

$\therefore \operatorname{SG}(2,2)=\operatorname{mex}\{0,2,2,0,3,3,1\}=4$，满足猜想。

还有一种特殊情况就是 $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}$，符合猜想。

证毕。

顺便挂一下代码：

#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
*/