C. Gerald and Giant Chess 详细题解

题目重述

在一个 $h \times w$ 的棋盘上，从左上角 $(1,1)$ 出发，每次只能向下或向右移动一格，目标是到达右下角 $(h,w)$。棋盘上有 $n$ 个黑色格子不能经过。求从起点到终点的路径总数，结果对 $10^9+7$ 取模。

数据范围：

• $1 \le h, w \le 10^5$，棋盘尺寸很大
• $1 \le n \le 2000$，黑色格子数量较少

核心思想

由于棋盘很大（$h,w$ 可达 $10^5$），无法对整个棋盘进行动态规划。但黑色格子很少（最多 $2000$ 个），我们可以利用容斥原理，只考虑这些障碍物对路径的影响。

第一步：无限制路径数

如果棋盘上没有黑色格子，从 $(1,1)$ 到 $(h,w)$ 需要向下走 $h-1$ 步，向右走 $w-1$ 步，总步数为 $h+w-2$。

从这 $h+w-2$ 步中选择 $h-1$ 步作为向下移动，其余为向右移动，因此路径数为：

$\binom{h+w-2}{h-1}$

第二步：容斥原理

设 $A_i$ 表示路径经过第 $i$ 个黑色格子的事件。根据容斥原理，不经过任何黑色格子的路径数为：

$\text{答案} = \sum_{S \subseteq \{1,2,\dots,n\}} (-1)^{|S|} \times (\text{经过 } S \text{ 中所有黑色格子的路径数})$

其中 $S$ 是黑色格子的子集。

第三步：容斥的优化

直接枚举所有子集需要 $O(2^n)$ 的时间，不可行。我们注意到：

• 经过多个黑色格子的路径，这些黑色格子必须按某种顺序排列（行坐标和列坐标都单调不减）
• 因此我们可以按坐标排序后，用动态规划来计算

排序

将所有黑色格子按行坐标升序排列，如果行坐标相同则按列坐标升序排列。这样，任何合法路径经过的黑色格子必然按照这个顺序出现。

动态规划状态

设 $dp[i]$ 表示从起点 $(1,1)$ 走到第 $i$ 个黑色格子，且不经过其他任何黑色格子的路径数。

状态转移方程

对于第 $i$ 个黑色格子 $(r_i, c_i)$：

1. 从 $(1,1)$ 到 $(r_i, c_i)$ 的无限制路径数为： $\binom{r_i + c_i - 2}{r_i - 1}$

2. 需要减去所有"先经过某个更早的黑色格子 $j$，再到达 $i$"的路径：

   • 从 $j$ 到 $i$ 的路径数：需要向下走 $r_i - r_j$ 步，向右走 $c_i - c_j$ 步，即： $\binom{(r_i - r_j) + (c_i - c_j)}{r_i - r_j}$
   • 乘以 $dp[j]$ 得到经过 $j$ 且不经过其他黑色格子，最终到达 $i$ 的路径数

因此转移方程为： $dp[i] = \binom{r_i + c_i - 2}{r_i - 1} - \sum_{j < i, r_j \le r_i, c_j \le c_i} dp[j] \times \binom{(r_i - r_j) + (c_i - c_j)}{r_i - r_j}$

最终答案

为了得到到终点的路径数，我们将终点 $(h,w)$ 视为第 $n+1$ 个格子（记为 $dp[n+1]$），按照同样的方法计算即可。

第四步：组合数计算

由于 $h,w \le 10^5$，$h+w \le 2 \times 10^5$，我们需要高效计算组合数 $\binom{n}{k} \bmod M$，其中 $M = 10^9+7$。

预处理方法

1. 预计算阶乘： $fac[i] = i! \bmod M, \quad i = 0, 1, \dots, h+w$

2. 计算阶乘的逆元： 利用费马小定理：$a^{-1} \equiv a^{M-2} \pmod{M}$

   • 先计算 $fac[h+w]$ 的逆元
   • 然后递推：$invfac[i-1] = invfac[i] \times i \bmod M$

3. 组合数公式： $\binom{n}{k} = \frac{n!}{k!(n-k)!} \equiv fac[n] \times invfac[k] \times invfac[n-k] \pmod{M}$

第五步：时间复杂度分析

• 预处理：$O(h+w)$，计算阶乘和逆元
• 排序：$O(n \log n)$，对黑色格子排序
• 动态规划：$O(n^2)$，因为需要枚举所有 $i$ 和 $j$

由于 $n \le 2000$，$n^2 = 4 \times 10^6$，完全可行。

第六步：正确性证明

容斥原理的合理性

设 $f(S)$ 表示经过 $S$ 中所有黑色格子的路径数。根据容斥原理： $\text{不经过任何黑格子的路径数} = \sum_{S \subseteq \{1,\dots,n\}} (-1)^{|S|} f(S)$

动态规划与容斥的关系

将黑色格子按坐标排序后，$dp[i]$ 实际上计算了： $dp[i] = \sum_{S \subseteq \{1,\dots,i-1\}, \text{按顺序}} (-1)^{|S|} f(S \cup \{i\})$ 其中 $f(S \cup \{i\})$ 表示经过 $S$ 中所有格子后再经过 $i$ 的路径数。

这等价于对以 $i$ 结尾的路径应用容斥原理，排除了所有经过其他黑色格子的情况。

终点处理

将终点视为第 $n+1$ 个格子，则： $dp[n+1] = \sum_{S \subseteq \{1,\dots,n\}} (-1)^{|S|} f(S \cup \{n+1\})$ 这正是从起点到终点、不经过任何黑色格子的路径数。

第七步：边界情况处理

1. 起点或终点为黑色格子：题目保证起点和终点是白色，无需特殊处理
2. $n=0$：直接输出 $\binom{h+w-2}{h-1}$
3. 路径需要经过多个黑色格子：如果这些格子不能按坐标单调递增排序，则 $f(S)=0$，动态规划会自动处理

第八步：模运算注意事项

由于结果需要对 $M = 10^9+7$ 取模：

• 所有乘法运算后及时取模
• 减法运算后加上 $M$ 再取模，避免负数
• 使用快速幂计算逆元

总结

本题的关键在于：

1. 利用 $n$ 小的特点：虽然棋盘很大，但障碍物很少，可以用容斥原理
2. 排序简化问题：按坐标排序后，路径经过的障碍物顺序是确定的
3. 动态规划实现容斥：$dp[i]$ 巧妙地计算了以 $i$ 结尾、不经过其他障碍物的路径数
4. 组合数预处理：高效计算路径数

这种"大棋盘小障碍"的问题，通过将障碍物作为关键点进行容斥 DP 是经典解法，时间复杂度 $O(n^2)$ 在 $n \le 2000$ 时完全可以接受。