题解

思路

无障碍时，从 $(x_1,y_1)$ 到 $(x_2,y_2)$ 的单调路径数为 $\binom{\Delta x+\Delta y}{\Delta x}$。把黑格与终点按行、列排序，可以只在这些关键点上做动态规划。

做法

令 $dp_i$ 为从起点到关键点 $i$ 且未经过更早黑格的路径数。先计算无障碍路径数，再减去所有能够到达 $i$ 的更早黑格 $j$ 的贡献 $dp_j\binom{\Delta x+\Delta y}{\Delta x}$。最后一个关键点是终点，其值即答案。

小棋盘可枚举所有下右路径；边长不超过 2000 时可在整个网格上做二维 DP。

正确性说明

任一经过黑格到达关键点 $i$ 的路径都有按排序最早遇到的黑格 $j$。按该最早黑格分类，贡献恰为到达 $j$ 且避开更早黑格的路径数乘 $j$ 到 $i$ 的无障碍路径数。各类互斥且覆盖所有非法路径，所以减法后恰为合法路径数。

复杂度

预处理阶乘后时间复杂度 $O(n^2+h+w)$，空间复杂度 $O(n+h+w)$。