MathLabs

第2题

考虑一个 100×100100\times100 的表格，将第 aa 行第 bb 列（1≤a,b≤1001\le a,b\le100）的格子等同于有序对 (a,b)(a,b)。设 kk 为满足 51≤k≤9951\le k\le99 的整数。一枚 kk-马是这样一种棋子：每次移动在竖直或水平方向走一格，在另一方向走 kk 格；即它从 (a,b)(a,b) 移动到 (c,d)(c,d)，使得 (∣a−c∣,∣b−d∣)(|a-c|,|b-d|) 等于 (1,k)(1,k) 或 (k,1)(k,1)。kk-马从格子 (1,1)(1,1) 出发并进行若干次移动。一个移动序列是指格子序列 (x0,y0)=(1,1),(x1,y1),…,(xn,yn)(x_0,y_0)=(1,1),(x_1,y_1),\ldots,(x_n,y_n)，使得对每个 i=1,2,…,ni=1,2,\ldots,n 都有 1≤xi,yi≤1001\le x_i,y_i\le100，且 kk-马能从 (xi−1,yi−1)(x_{i-1},y_{i-1}) 移动到 (xi,yi)(x_i,y_i)。此时每个格子 (xi,yi)(x_i,y_i) 称为可达的。对每个 kk，求可达格子的数目 L(k)L(k)。
第 4/5 步：S 之外每种颜色一个连通分量
上一步下一步
x+y≡1 ⁣ ⁣(mod2)  ⟹  (x,y) joined to (1,1) outside Sx+y\equiv1\!\!\pmod2\implies(x,y)\text{ joined to }(1,1)\text{ outside }S
详细分析

重复上一步的滑动，可以用一串两步路径把 SS 之外任意一格与 SS 之外、x+yx+y 奇偶性相同的另一格连接起来，因为每条两步路径都使 x+yx+y 改变一个偶数量，±2\pm2 或 ±2k\pm2k。因此 SS 之外与 (1,1)(1,1) 同色（即 x+yx+y 为偶）的所有格子都在包含 (1,1)(1,1) 的同一个连通分量中。