P5376 [THUPC 2019] 过河卒二 题解

（怎么题解区就我的做法是 $O(2^kk+k^2m)$ 的）

首先发现卒可以从棋盘的上方或右方走出棋盘等价于卒最后走到 $(n+1,m+1)$，因为卒走出方格以后到 $(n+1,m+1)$ 的路径是唯一的。

先不考虑卒从 $(x,y)$ 走到 $(x+1,y+1)$ 这种情况和障碍，那么由过河卒的熟知结论，从 $(1,1)$ 走到 $(n+1,m+1)$ 有方案数为 $C_{n+m}^n$，可以理解为从要走的 $m+n$ 步中选出 $n$ 步沿 $x$ 轴走。

然后我们考虑一下卒从 $(x,y)$ 走到 $(x+1,y+1)$ 怎么处理。考虑直接暴力枚举这样走的次数，那么设从 $(1,1)$ 走到 $(x+1,y+1)$ 的方案数为 $\sum\limits_{i=0}^{\min(n,m)}C_{n+m-i}^{i}\times C_{n+m-2i}^{n-i}$（其实看一下式子基本都能理解），使用 Lucas 定理求解。

接下来考虑障碍的情况。发现障碍很少，那么我们可以 $O(2^k)$ 枚举选哪些障碍，用容斥原理计算。可以通过 $O(k^2m)$ 预处理任意两个障碍之间的方案数来降低复杂度。

总复杂度 $O(2^kk+k^2m)$，代码写得比较丑就不放了。