「CEOI2020」象棋世界 题解

题目大意

棋盘 $R \times C$，$R$ 很大（$10^9$），$C \leq 1000$。
五种棋子从 $(1, c_1)$ 走到 $(R, c_R)$，求最少步数和方案数（模 $10^9+7$）。

解法分析

1. 兵（P）

• 移动：只能向下走一格，列不变。
• 判断：
  • 若 $c_1 \neq c_R$：无法到达，输出 0 0
  • 否则：$$\text{步数} = R - 1,\quad \text{方案数} = 1$$

2. 车（R）

• 移动：沿行或列任意格。
• 判断：
  • 若 $c_1 = c_R$：直接向下一步到达$$\text{步数} = 1,\quad \text{方案数} = 1$$
  • 否则：需要 $2$ 步（竖-横 或 横-竖）$$\text{步数} = 2,\quad \text{方案数} = R$$ 因为可以在任意一行转弯，共 $R$ 种方案。

3. 象（B）

• 移动：沿对角线移动，颜色由 $(r+c) \bmod 2$ 决定。
• 判断：
  • 若 $(1+c_1) \bmod 2 \neq (R+c_R) \bmod 2$：颜色不同，无法到达，输出 0 0
  • 否则：
    • 若 $|c_R - c_1| = R - 1$：在同一条对角线上，一步到达$$\text{步数} = 1,\quad \text{方案数} = 1$$
    • 否则：需要 $2$ 步$$\text{步数} = 2$$ 方案数 = 中间格个数。
      设中间格为 $(k, m)$，满足：$$k - 1 = |m - c_1|,\quad R - k = |c_R - m|$$ 解此方程组得到 $m$ 的取值个数即为方案数。

4. 后（Q）

• 移动：车 + 象的结合。
• 判断：

  • 如果满足以下任一条件，则一步可达（方案数 = 1）：

    1. $c_1 = c_R$（竖直线）
    2. $|c_R - c_1| = R - 1$（对角线）
    3. $(1+c_1) \bmod 2 = (R+c_R) \bmod 2$（颜色相同，但未必在同一条对角线） 实际上第3条是象的必达条件，但后可以直接走车的一步+象的一步？这里要修正：

    正确一步条件：

    • 在同一行/列：$c_1 = c_R$
    • 在同一对角线：$|c_R - c_1| = R - 1$
    • 实际上后一步可达当且仅当 $c_1 = c_R$ 或 $|c_R - c_1| = R - 1$ 或 $R = 1$（但 $R \ge 2$），因为后可以走直线或斜线，但一步从 $(1,c_1)$ 到 $(R,c_R)$ 需要 $|c_R - c_1| = R - 1$ 或 $c_1 = c_R$。

  • 否则：需要 $2$ 步

    $$\text{步数} = 2$$

    方案数 = 车的 $2$ 步方案数 + 象的 $2$ 步方案数
    即：

    $$\text{方案数} = R + \text{象的2步方案数}$$

5. 王（K）

• 移动：八邻格。

• 最少步数：

  $$\text{步数} = \max(R - 1, |c_R - c_1|)$$

  因为每步最多在行方向前进 1，列方向最多变化 1。

• 方案数： 设 $dp[r][c]$ 表示走到 $(r, c)$ 的最少步数方案数。
  转移：

  $$dp[r][c] = \sum_{dc=-1}^{1} dp[r-1][c+dc]$$

  但 $R$ 很大，使用矩阵快速幂优化：

  • 状态：当前行的所有列 $[1, C]$
  • 转移矩阵 $M$：$M_{i,j} = 1$ 当 $|i-j| \le 1$，否则 $0$
  • 初始向量：$v_{c_1} = 1$，其余 $0$
  • 答案：$(M^{R-1} \cdot v)_{c_R}$

  复杂度 $O(C^3 \log R)$，可接受（$C \le 1000$ 时用优化矩阵乘法）。

总结

本题需要针对每种棋子特性分别处理：

• P、R、B、Q 主要靠数学推导和组合计数
• K 需要动态规划 + 矩阵快速幂
• 注意 $R$ 很大时的模运算和高效计算

实现时注意边界情况和模数处理即可。