AT4546 题解
GaryH
2021-09-04 14:57:19
# AT4546 题解
一道简单的计数题。
首先可以想到一种简单而暴力的DP方法：
计 $dp(i,j)$ 代表原地图中从 $(1,1)$ 走到 $(i,j)$ ，不经过任何障碍的方案数，那么 $dp(h,w)$ 即为答案。
但是这样无论是时间复杂度还是空间复杂度都会爆炸，所以我们需要优化不必要且繁琐的状态。
首先假设地图中没有障碍，那么这样的方案数可以用组合数算，即:
在一张无障碍的地图中，从 $(1,1)$ 走到 $(i,j)$ 的方案数为：
$\dbinom {i+j-2}{i-1}$
至于原因，是可以把一条路径的走法理解为，从 $i+j-2$ 次移动中选择 $i-1$ 次向下，其他的向右，而按这样选择的走就一定能到达点 $(i,j)$ 。
那如果地图中有一个障碍呢？
这样就不好用组合数直接统计了，实际上在这种情况下，直接正方向的计算并不轻松，那正难则反，我们就考虑如何把所有路径中，经过了障碍的给去掉。
于是我们来计算所有经过了障碍的路径：
设障碍的位置为 $(x,y)$ , 则经过障碍的方案数为，
从 $(1,1)$ 到 $(x,y)$ 的方案数与从 $(x,y)$ 到 $(h,w)$ 的方案数之积。
一个障碍的方案数计算出来了，那再加一个障碍呢？再加 $n$ 个障碍呢？
一种暴力的方法就是，把每个经过一个障碍的路径从总方案数里去掉，在把所有经过两个障碍的路径加回来，再把三条的删去，...... 诸如此类，用容斥的思想把答案计算出来。但这样的复杂度实在不能接受，故我们要考虑一种不会算重的计数方法，以省略掉复杂度极高的枚举和容斥。
于是我们可以计 $dp(i)$ 代表从 $(1,1)$ 到第 $i$ 个障碍 $(x_i,y_i)$ ，中间不经过其他障碍的方案数。当然，我们可以令 $(h,w)$ 为第 $n+1$ 个障碍，那么答案就是 $dp(n+1)$ 。
我们发现，可以合理的利用以前计算过的方案数不重不漏地推出当前的状态，即：
$dp(i)= \tbinom {x_i+y_i-2}{x_i-1}- \sum_{j=1}^{i-1}{dp(j) \times \tbinom {x_i-x_j+y_i-y_j}{x_i-x_j}} $
看起来这个似乎很像把经过一个障碍的方案数扣掉了，就不管了？那为什么是对的呢？
实际上，这个和扣掉一个点的方法并不一样，因为 $dp(i)$ 记录的是不经过任何障碍的方案数，
故上面的转移方程式中， $\sum_{j=1}^{i-1}{dp(j) \times \tbinom {x_i-x_j+y_i-y_j}{x_i-x_j}}$ 所去除掉的路径都一定是不重不漏的，因为任意一个 $j$ 对应的都是第一次经过障碍 $j$ 的方案数，而和式中任意一个小于 $j$ 的 $k$ ，$k$ 在和式中去掉的路径第一次经过的障碍都不是 $j$ ，所以一定没有被多次去除掉的路径，这就是对于上述转移方程式的正确性证明。
那么我们只要预处理出阶乘以及其逆元，从而 $O(1)$ 的计算组合数即可。
因为计算某一个 $i$ 的方案数所用的时间是 $O(n)$ 级别的，所以总复杂度是 $O(n^2)$ 的。
**Code**:
```
const int N(3e5+10);
const int mod(1e9+7);
int n,h,w;
int dp[N];
int inv[N];
int fiv[N];
pair < int , int > p[N] ;
inline int ksm(int a,int b){
int res=1;
while(b){
if(b&1)(res*=a)%=mod;
(a*=a)%=mod,b>>=1;
} return res%mod;
}
inline int C(int x,int y){
return (inv[x]*fiv[y]%mod)*fiv[x-y]%mod;
}
signed main(){
h=read(),w=read(),n=read();
rep(i,1,n)p[i].fi=read(),p[i].se=read();
p[n+1].fi=h,p[n+1].se=w;
sort(p+1,p+n+1),inv[0]=fiv[0]=1;
rep(i,1,N-10ll)inv[i]=(inv[i-1]*i)%mod,fiv[i]=ksm(inv[i],mod-2);
dp[0]=1ll,p[0].fi=p[0].se=1;
rep(i,1,n+1){ dp[i]=C(p[i].fi+p[i].se-2,p[i].fi-1)%mod;
rep(j,1,i-1){
if(p[j].fi>p[i].fi||p[j].se>p[i].se)continue;
int XL=p[i].fi-p[j].fi,YL=p[i].se-p[j].se;
dp[i]-=dp[j]*C(XL+YL,XL)%mod,dp[i]=(dp[i]+mod)%mod;
} }
cout<<dp[n+1]%mod;
return 0;
}
```