【BZOJ1434】【ZJOI2009】染色游戏（SG函数）

函数）"/>

【BZOJ1434】【ZJOI2009】染色游戏（SG函数）

Description

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

Solution

参考博客：
（坐标起始点为 (0,0) ( 0 , 0 ) $(0,0)$）
设 g(i,j) g ( i , j ) $g(i,j)$为局面中只有 (i,j) ( i , j ) $(i,j)$一个位置上为反面时的SG函数。
则 g(0,0)=1 g ( 0 , 0 ) = 1 $g(0,0)=1$， g(0,1)=2 g ( 0 , 1 ) = 2 $g(0,1)=2$， g(0,2)=1… g ( 0 , 2 ) = 1 … $g(0,2)=1\dots$
g(1,1)=mex{0,g(0,0),g(0,1),g(1,0),g(1,0)⊕g(0,1),…} g ( 1 , 1 ) = m e x { 0 , g ( 0 , 0 ) , g ( 0 , 1 ) , g ( 1 , 0 ) , g ( 1 , 0 ) ⊕ g ( 0 , 1 ) , … } $g(1,1)=mex\{0,g(0,0),g(0,1),g(1,0),g(1,0)\oplus g(0,1),\dots\}$
推(da)导(biao)发现规律：
若 ij=0 i j = 0 $ij=0$，则 g(i,j)=lowbit(i+j+1) g ( i , j ) = l o w b i t ( i + j + 1 ) $g(i,j)=lowbit(i+j+1)$
否则 g(i,j)=2i+j g ( i , j ) = 2 i + j $g(i,j)=2^{i+j}$

Source

/************************************************* Au: Hany01* Date: Mar 12th, 2018* Prob: [BZOJ1434][ZJOI2009] 染色问题* Email: hany01@foxmail
************************************************/#include<bits/stdc++.h>using namespace std;typedef long long LL;
typedef pair<int, int> PII;
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define fir first
#define sec second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define ALL(a) (a).begin(), (a).end()
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define Mod (1000000007)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaiatemplate <typename T> inline bool chkmax(T &a, T b) { return a < b ? a = b, 1 : 0; }
template <typename T> inline bool chkmin(T &a, T b) { return b < a ? a = b, 1 : 0; }inline int read()
{register int _, __; register char c_;for (_ = 0, __ = 1, c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -1;for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << 1) + (_ << 3) + (c_ ^ 48);return _ * __;
}inline void File()
{
#ifdef hany01freopen("bzoj1434.in", "r", stdin);freopen("bzoj1434.out", "w", stdout);
#endif
}#define lb(x) ((x) & -(x))
int main()
{File();static bool bit[300];static int Log[300];static char type;For(i, 0, 8) Log[1 << i] = i;for (register int T = read(); T --; ){register int n = read(), m = read(), mark = 0;Set(bit, 0);rep(i, n) rep(j, m) {scanf(" %c", &type);if (type == 'T') if (!(i * j)) bit[Log[lb(i + j + 1)]] ^= 1; else bit[i + j] ^= 1;}rep(i, 250) if (bit[i]) { mark = 1; break; }puts(mark ? "-_-" : "=_=");}return 0;
}
//闲云潭影日悠悠，物换星移几度秋。
//    -- 王勃《滕王阁序》