51nod 1486 大大走格子[容斥原理]

题面传送门

题解

好早以前就考过,当时根本不会

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 ;
}