做法其他题解已经说得很清楚了，但似乎没有对于本题 SG 函数正确性的证明，我来口胡一下（
证明：
猜想：
我们要用到一个结论： 局面的 SG 值等于局面中所有反面朝上的硬币单独存在时的 SG 值的异或和 。然而这个结论我不太会证（）。我们暂且使用它而不证明。
首先当 (i=1lor j=1) 成立时，本题相当于一维放硬币问题，其 SG 函数等同于一维的 (lowbit(i))。因为 (i) 或 (j) 中至少有一个是 1，于是我们只需要将横纵坐标相加再 (-1) 即可消去为 1 的那一维。
对于其他情况我们使用数学归纳法：
首先对于 (operatorname{SG}(2,2)) ，有以下几种选择方案（下图中 (0/1) 代表反转后分别是正面/反面朝上）：
(egin{matrix} 0&0\0&0 end{matrix} ,operatorname{SG}=0)
(egin{matrix} 0&1\0&0 end{matrix} ,operatorname{SG}=operatorname{SG}(1,2)=2)
(egin{matrix} 0&0\1&0 end{matrix} ,operatorname{SG}=operatorname{SG}(2,1)=2)
(egin{matrix} 0&1\1&0 end{matrix} ,operatorname{SG}=operatorname{SG}(1,2)spaceoperatorname{xor}space operatorname{SG}(2,1)=0)
(egin{matrix} 1&1\0&0 end{matrix} ,operatorname{SG}=operatorname{SG}(1,1)spaceoperatorname{xor}space operatorname{SG}(1,2)=3)
(egin{matrix} 1&0\1&0 end{matrix} ,operatorname{SG}=operatorname{SG}(1,1)spaceoperatorname{xor}space operatorname{SG}(2,1)=3)
(egin{matrix} 1&1\1&0 end{matrix} ,operatorname{SG}=operatorname{SG}(1,1)spaceoperatorname{xor}space SG(1,2)spaceoperatorname{xor}space operatorname{SG}(2,1)=1)
( herefore operatorname{SG}(2,2)=operatorname{mex}{0,2,2,0,3,3,1}=4)，满足猜想。
还有一种特殊情况就是 (i=2land j>2) 或 (i>2land j=2)，不难发现它们是等价的，因此这里我们只以 (i=2land 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}spaceoperatorname{xor}space[0,2^{i+j-3}-1]) 即 ([2^{i+j-3},2^{i+j-2}-1]) 范围内的值；可以证明在 (jge3) 时有 (operatorname{SG}(i-1,j)=operatorname{lowbit}(j)le 2^{i+j-4}) （在 (j=3) 时有 (operatorname{lowbit}(3)=1le 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)spaceoperatorname{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>2land 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}spaceoperatorname{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("-_-
");
else printf("=_=
");
}
return 0;
}
/*
1
3 4
TTHH
THTH
TTHH
*/