简单奶龙题。

原题中 W,H,L,R,D,UW, H, L, R, D, U 分别对应题解中 n,m,u,d,l,rn, m, u, d, l, r。定义原题目答案为 solve(n,m,u,d,l,r)\mathrm{solve}(n, m, u, d, l, r)。

定义 S1(n,m)S1(n, m) 为 [0,n]×[0,m][0, n] \times [0, m] 的矩形中从 (0,0)(0, 0) 出发的路径条数，S2(n,m)S2(n, m) 为总路径条数，有 S1(n,m)=(n+m+2m+1),S2(n,m)=(n+m+4m+2)−(n+2)(m+2)−1S1(n, m) = \binom{n + m + 2}{m + 1}, S2(n, m) = \binom{n + m + 4}{m + 2} - (n + 2)(m + 2) - 1，证明略。

先考虑求 (0,0)(0, 0) 到 (n,m)(n, m) 的路径数。网格图障碍行走问题考虑经典容斥，设 fif_i 为之前未接触过障碍走到第 ii 个障碍的方案数。发现该矩形中只有第一行和第一列的 ff 值非 00，那么转移最多只有两层，预处理后可以 O(r−l+d−u)O(r - l + d - u) 计算。

接下来考虑求 solve(n,m,u,d,l,r)\mathrm{solve}(n, m, u, d, l, r)。还是考虑用总路径数减去非法路径数，然后枚举路径上第一个障碍，那么合法的起点终点都在一个矩形内且互相独立。但注意 第一个障碍一定在第一行或第一列 需要在 起终点都是合法点 的基础上才成立，所以前面的总路径数实际上是 起终点都是合法点 的路径数。这个也考虑容斥，用 S2(n,m)S2(n, m) 减掉 起点非法终点合法、起点合法终点非法、起终点均非法。注意到第三种路径直接就是 S2(d−u,r−l)S2(d - u, r - l)；第一种路径的第一个障碍也一定在第一行或第一列，可以在上面的过程中一起减掉；第二种路径相当于把网格翻转之后的第一种路径，可以用一样的方式求（或者有一种更聪明的方法：第二种路径的个数是 S2(n−u,m−l)−solve(n−u,m−l,n−d,n−u,m−r,m−l)S2(n - u, m - l) - \mathrm{solve}(n - u, m - l, n - d, n - u, m - r, m - l)，且递归之后的 solve\mathrm{solve} 不存在第二种路径）。

那么这题就做完了，时间复杂度为 O(n+m)O(n + m)。code。