题解 SP7602 【CF36D - New Game with a Chess Piece】

A_Pikachu · 2020-04-23 22:08:17 · 题解

题目传送门

（如果 \LaTeX 炸了，请到博客观看）

这里是人话理解题目：在一个 n \times m 的棋盘上，(1,1) 的位置有一个棋子，这个棋子每次能往下走一格或往右走一格或往右下移动 k 格，每次移动不能超出棋盘，如果棋子恰好移动到 (n,m) 则移动的人赢，问你如果你先手（先移动），你是否有必胜策略。

不难想，当 n,m 比较小时，我们能够用简单的有向无环图解决，但这里 1 \leq n,m \leq 10^{9}，所以这题就变成了一道博弈论的题目。

现在已知 n,m,k，我们不妨设 f\ (\ i\ ,\ j\ ) 表示当棋子在 (\ i\ ,\ j\ ) 时，先手是否能获胜，特别地，f\ (\ 1\ ,\ 1\ )=0。那么根据我们的定义，f\ (\ i\ ,\ j\ )=\neg\ \Big(\ f\ (\ i-1\ ,\ j\ )\ \land\ f\ (\ i\ ,\ j-1\ )\ \land\ f\ (\ i-k\ ,\ j-k\ )\ \Big)，而且超出棋盘外的地方不会参与运算。

那么我们现在就来分析 f\ (\ n\ ,\ m\ ) 的规律。很容易发现，在第一行或第一列时，能够影响这个点的值只有第一行的上一列或第一列的上一行，又已知 f\ (\ 1\ ,\ 1\ )=0 ，所以第一行和第一列的 f 值均是 0,1 交替出现的。接下来 k-1 行和 k-1 列，由于 f\ (\ i\ ,\ j\ ) 不受 f\ (\ i-k\ ,\ j-k\ ) 的影响，所以f\ (\ i\ ,\ j\ )=\neg\ \Big(\ f\ (\ i-1\ ,\ j\ )\ \land\ f\ (\ i\ ,\ j-1\ )\ \Big)，又由于第一行和第一列的值是 0,1 交替出现的，所以前 k 行和前 k 列均是 0,1 交替的。如下是 k=3 时的 f 值：

通过上表可知，在第 k+1 行的第 k 列及 k+1 列的第 k 行后的每个数均为 1，即均能获胜。因为在第 k+1 行第 i 列或在第 k+1 列第 i 行时，若 (i-k)\equiv 1\pmod 2 则第 1 行第 i-k 列或第 i-k 行第 1 列一定为 0，反之，第 k-1 行第 i 列或第 i 行第 k-1 列一定为 0。于是，就填出了下表：

再往下填 k 行和 k 列时，发现 \ f\ (\ i\ ,\ j\ )=\neg \ f\ (\ i-k-1\ ,\ j-k-1\ )， （具体证明略，） 自然，再往下填 1 行 1 列时，这 1 行 1 列均为 1。需要注意的情况是在第 n \times (k+1) 行第 m 列时，若 m < n \times (k+1)，则其满足的情况为 0,1 交替。

而且不难发现，f 的值具有对称型，所以 f\ (\ n\ ,\ m\ )=f\ (\ m\ ,\ n\ )，这对于需要特别判断大小的情况比较方便。

然后要注意的是当 k=1 时，需要特判（因为这时不满足 \ f\ (\ i\ ,\ j\ )=\neg \ f\ (\ i-k-1\ ,\ j-k-1\ ) 的性质）。