題面傳送門
題解
好早以前就考過,當時根本不會
O(nm) 的dp很簡單,但是不夠用啊。考慮通過障礙物轉移,從 (x1,y1) 到 (x2,y2) 的方案數就是 C(x2−x1,x2−x1+y2−y1) ,就是想想總共走多少步中選幾步往下走,把起點終點加到障礙物裡一起轉移。
先按坐标排個序,設 f[i] 為前i個障礙物隻經過第i個的方案數, f[i]=C(xi−1,xi+yi−2)Σf[i]∗C(xi−xj,xi−xj+yi−yj) (j<i) 。
逆元預處理一下就好
#include<cstdio>
#include<algorithm>
#define P 1000000007
#define LL long long
using namespace std;
int h,w,n,fac[],inv[];
LL f[];
struct node{
int x,y;
bool operator < (const node &b) const {
return x<b.x||(x==b.x&&y<b.y);
}
}a[];
inline void Pre(int n){
int i;
for(fac[]=,i=;i<=n;++i) fac[i]=ll*fac[i-]*i%P;
for(inv[]=inv[]=,i=;i<=n;++i) inv[i]=ll*(P-P/i)*inv[P%i]%P;
for(i=;i<=n;++i) inv[i]=ll*inv[i]*inv[i-]%P;
}
inline int C(int x,int y){return ll*fac[y]*inv[x]%P*inv[y-x]%P;}
inline int calc(int i,int j){
return C(a[i].x-a[j].x,a[i].x-a[j].x+a[i].y-a[j].y);
}
int main(){
scanf("%d%d%d",&h,&w,&n);
Pre(h+w);
for(int i=;i<=n;++i) scanf("%d%d",&a[i].x,&a[i].y);
a[++n]=(node){h,w};a[]=(node){,};
sort(a+,a+n+);
for(int i=;i<=n;++i){
f[i]=calc(i,);
for(int j=;j<i;++j){
if(a[j].y<=a[i].y)
f[i]=(ll*f[i]-f[j]*calc(i,j)%P+P)%P;
}
}
printf("%lld\n",f[n]);
return ;
}