CF36D New Game with a Chess Piece 题解

前言：

都大半年没在洛谷上提交过题解了。

SPOJ 上有双倍经验，题号为 SP7602。

我看题解区的大佬们有的正经用博弈论做，有的打表，但是感觉没有讲得很形象，这篇题解将生动讲述打表做法，同时为了让大家在感性理解后，还可以理性理解，会附上证明（这部分参考了别的题解）。

正文：

Step 1：打表找规律

令 \(b_{i,j}\) 表示从第 \(i\) 行第 \(j\) 列出发，是胜还是败。如果胜，\(b_{i,j}=1\)，否则 \(b_{i,j}=0\)。

我们先不考虑越界的问题，如果 \(b_{i+1,j},b_{i,j+1},b_{i+k,j+k}\) 中至少有一个为零（具体意义就是，从第 \(i\) 行第 \(j\) 列出发可以走到一个对手会败的位置），那么 \(b_{i,j}=1\)，否则 \(b_{i,j}=0\)。

也就是说，\(b_{i,j}=\lnot(b_{i+1,j} \bigwedge b_{i,j+1} \bigwedge b_{i+k,j+k})\)。

状态转移时，如果越界的话，那么那个越界的值就不参与运算，所以为了方便起见，可以设它为 1.

附上打表程序

为了直观，我先搞一张表来给大家解释：

0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0
1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1 0 1 1 0 1 0 1 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0 1 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 1 0 1 0
1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0
0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0