P2594 [ZJOI2009] 染色游戏

$$$$

题目描述

一共 $n\times m$ 个硬币，摆成 $n\times m$ 的长方形。dongdong 和 xixi 玩一个游戏，每次可以选择一个连通块，并把其中的硬币全部翻转，但是需要满足存在一个硬币属于这个连通块并且所有其他硬币都在它的左上方（可以正左方也可以正上方），并且这个硬币是从反面向上翻成正面向上。dongdong 和 xixi 轮流操作。如果某一方无法操作，那么他（她）就输了。dongdong 先进行第一步操作，假设双方都采用最优策略。问 dongdong 是否有必胜策略。

输入格式

第一行一个数 $T$，表示他们一共玩 $T$ 局游戏。

接下来是 $T$ 组游戏描述。每组游戏第一行两个数 $n,m$。

接下来 $n$ 行每行 $m$ 个字符，第 $i$ 行第 $j$ 个字符如果是 H 表示第 $i$ 行第 $j$ 列的硬币是正面向上，否则是反面向上。第 $i$ 行 $j$ 列的左上方是指行不超过 $i$ 并且列不超过 $j$ 的区域。

输出格式

对于每局游戏，输出一行。如果 dongdong 存在必胜策略则输出 -_- 否则输出 =_=（注意输出的都是半角符号，即三个符号 ASCII 码分别为 45，61，95）。

输入输出样例 #1

输入 #1

3
2 3
HHH
HHH
2 3
HHH
TTH
2 1
T
H

输出 #1

=_=
-_-
-_-

说明/提示

对于 $40\mathrm{\%}$ 的数据，满足 $1\le n,m\le 5$。

对于 $100\mathrm{\%}$ 的数据，满足 $1\le n,m\le 100，1\le T\le 50$。

题解

显然，终止状态是所有硬币都正面向上。我们可以将整个游戏分解为将每个反面朝上的硬币翻到正面朝上的过程。

提出一个定理：整个局面的 SG 函数等于各个反面朝上的硬币单独存在时的 SG 函数异或和。换言之，整个局面可以按照反面向上的硬币分解即为若干个游戏，其中每个游戏只有一个反面朝上的硬币。例如：

HHH
TTH

可以被分解为这两个游戏

HHH     HHH
THH     HTH

这一分解的合法性可用数学归纳法证明：

首先考虑一维的问题。我们给每个一维的局面分配一个分数，从左到右的第 $i$ 个硬币若为 H 计 0 分，若为 T 计 $2^i$ 分。例如 HHTHT 局面的分数为 $4+16=20$。每次翻转的整个联通块中必然最右侧的硬币是从 T 翻转到 H，翻转后整个局面的分数必然减少。

我们可以证明分数为 0 的局面 HHHHH 满足定理。

我们可以证明若分数为 $\mathrm{\forall }k<k_0$ 的局面都满足定理，则分数为 $k_0$ 的局面满足定理。

对于二维的问题，可以简单地扩展分数计算规则。

对于每个硬币的 SG 函数值，进行打表找规律：

$$\mathrm{SG}(i,j)=\{\begin{array}{cc}lowbit(i+j-1)& \text{ if }i=1\vee j=1\\ 2^{i+j-2}& \text{ else }\end{array}$$

SG 函数值最大可达 $2^{198}$ 级别，使用 bitset 来储存。