[ZJOI2009]染色游戏

Time Limit:5000MS  Memory Limit:65536K
Total Submit:22 Accepted:13
Case Time Limit:1000MS

Description

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

Input

第一行一个数T，表示他们一共玩T 局游戏。接下来是T 组游戏描述。每
组游戏第一行两个数n;m，接下来n 行每行m 个字符，第i 行第j 个字符如
果是“H” 表示第i 行第j 列的硬币是正面向上，否则是反面向上。第i 行j 列
的左上方是指行不超过i 并且列不超过j 的区域。

Output

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

Sample Input

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

Sample Output

= =
– –
– –

Hint

对于40% 的数据，满足1 ≤ n;m ≤ 5。
对于100% 的数据，满足1 ≤ n;m ≤ 100，1 ≤ T ≤ 50。

Source
这个题目一看就知道是要算SG函数的破题。。很多年
以前我看到这题就哆嗦囧。。不过今天研究了一个晚上
各种文献算是会做了瀑布汗。。。
首先肯定是要算SG函数值的，设点(x,y)的函数值为F(x,y)
先证个好证的：
当x和y都大于0的时候，F(x,y)=2^(x+y)..
终态就是没有一个T囧。。SG（终态）=0
首先使用归纳法，为了方便吧(0,0),(0,1),(1,0)也考虑进去，
这些点显然满足条件。。
然后开始用x+y=k,按k归纳。。
假设k-1没问题了。。
那么要证明k的话，就要证明以(x,y)为最右下的有联通块的SG值为0..2^(x+y)-1,且没有2^(x+y)。。
后者是显然的，因为（x，y）是最右下，所以其它的点在x+y这位上都是0。。怎么也不会弄出个2^(x+y)。
前者也可以构造出来。。具体的说就是给定个数X，如果它在第i位上是0，那么我就在x+y=i那条线上弄两个点，否则就弄一个。。YY一下就可以了。。
再证个麻烦的。。
当x=0或y=0的时候，显然上面对证法就不能成立囧。。
但此时已经变成一个经典的一维问题了，决策也是O（N）
的。。所以弄个N^2的Dp算下SG值就可以了。。
不过还是讲一下更加数学化的做法吧，
这个问题叫Ruler游戏。。
就是给你一条硬币，每次翻连续的一段，最后一个一定是由
反面到正面。。
设F(x)为第x个硬币的SG值。。
那么可以证明F(x)为可以将x整除的2的最大幂。。
用归纳法搞一下就可以了。。。
话说这个题目真TMD猥琐。。输出不对的。。
看哪个ASCII的号码的话应该是=_=he-_-才对啊囧。。。
Code：

#include <cstdio>
#include <cstring>
#define rep(i,n) for(int i=0;i<n;i++)
const int inf=~0U>>1,maxn=105;
using namespace std;
inline int lowbit(int x){return x&-x;}
int log(int x){return x==1?0:(log(x/2)+1);}
int n,m;
int sg(int x,int y)
{
if(x==0||y==0)return log(lowbit(x+y+1));
return x+y;
}
bool E[maxn*2]={};
int main()
{
//freopen("in","r",stdin);
int T;scanf("%d",&T);
rep(t,T)
{
scanf("%d%d",&n,&m);
memset(E,0,sizeof E);
rep(i,n)
{
scanf(" ");
rep(j,m)
{
char c=getchar();
if(c==’T’)
E[sg(i,j)]^=1;
}
}
bool ok=true;
rep(i,n+m)if(E[i]){ok=false;break;}
if(ok)puts("=_=");
else puts("-_-");
}
}