CF-559C Gerald and Giant Chess

CF-559C Gerald and Giant Chess / AtCoder DP-Y Grid 2 给定一个 $H*W$ 的棋盘，棋盘上只有 $N$ 个格子是黑色的，其他格子都是白色的。在棋盘左上角有一个卒，每一步可以向右或者向下移动一格，并且不能移动到黑色格子中。求这个卒从左上角移动到右下角，一共有多少种可能的路线。 $(1 ≤ h, w ≤ 105, 1 ≤ n ≤ 2000)$ $O(hw)$ 的暴力 DP 很好想，但是过不了。 假设没有障碍，从 $(1, 1)$ 到 $(i, j)$ 的方案数是 $C_{i+j-2}^{i-1}$（等于 $C_{i+j-2}^{j-1}$）。可以这么理解：可以用 $D, R$ 来表示一条路径，那么从 $(1, 1)$ 到 $(i, j)$ 的路径中有 $i-1$ 个 $D$ 和 $j-1$ 个 $R$。于是问题转化为从 $i+j-2$ 个位置中选 $i-1$ 个放 $D$ 的方案数。 如果有一个障碍，从正面统计方案数很困难，正难则反，考虑将总的方案数减去经过障碍的方案数。假设障碍的位置是 $(x, y)$，终点是 $(h, w)$，经过障碍的方案数就是 $C_{x+y-2}^{x-1} * C_{h-x+w-y}^{h-x}$（乘法原理）。

• #chess