题解：P17863 中秋 / plenilune

xxxxxzy · 2026-11-08 18:22:18 · 题解

upd on 26.11.09：gpt 发现讨论漏了一个情况。

首先一个事情是方向存在某种对称性，由于 0 和 2 是对称的，3 和 7 是对称的，4 和 6 是对称的，所以我们的讨论量可以减半。

下面只呈现所有有解的情况（对称的会略去），一些不太平凡的情况用 * 标记出来了：

(0,2,4)：

合法条件是 [n \equiv 1 \bmod 2]，比较显然。

(0,2,5)：

合法条件是 [(n-1)(m-1) \equiv 0 \bmod 3]。

对原图三染色，坐标 (i,j) 的颜色是 (i+j \bmod 3)，每次行走颜色必然 +1，起点是 2，终点是 n+m \bmod 3，经过了 nm-1 步，那么需要满足 [nm+1 \equiv n+m \bmod 3]。然后有合法性构造，构造是平凡的，略去。

(0,3,5)：

合法条件是 [m \equiv 2 \bmod 4]，构造大概长这样：

*(0,3,6)：

同样三染色，但是 (i,j) 的颜色为 (j-i \bmod 3)，(1,1) 的颜色为 0，(n,m) 的颜色为 (m-n) \bmod 3，那么有 [0+nm-1 \equiv m-n \bmod 3]，也就是 [(m+1)(n-1) \equiv 0 \bmod 3]。

其中 m 的一项显然有合法性构造，n 的那一项对于 m>4 均可行，有一个不太平凡的构造。大概长这样：

(0,1,2,4)：

和 (0,2,4) 答案一样。

(0,1,2,5)：

首先会继承 (0,2,5) 的答案 [(n-1)(m-1) \equiv 0 \bmod 3]。但是我们惊讶地发现，使用这四个方向向量远远强于原来的三个。具体来说，下面我们证明对于 n,m 不为 3 时，一定可以全部遍历网格。

首先我们发现，如果 n \times m 是合法的，那么 (n+3) \times m, n \times (m+3) 必定也是合法的，因为考虑如下结构：

这个结构可以缩减 3 \times n，对称一下可以缩减 n \times 3。也就是说，问题被缩减到了 (5,5),(5,6),(6,5),(6,6) 四种，中间两种显然是对称的，也就是说我们只需要对这三种情况手动构造即可。下面给出手动构造：