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)，代码写得比较丑就不放了。