51nod 1486 大大走格子—

有一个h行w列的棋盘，里面有一些格子是不能走的，现在要求从左上角走到右下角的方案数。

Input

单组测试数据。

第一行有三个整数h, w, n(1 ≤ h, w ≤ 10^5, 1 ≤ n ≤ 2000)，表示棋盘的行和列，还有不能走的格子的数目。

接下来n行描述格子，第i行有两个整数ri, ci (1 ≤ ri ≤ h, 1 ≤ ci ≤ w)，表示格子所在的行和列。

输入保证起点和终点不会有不能走的格子。

Output

输出答案对1000000007取余的结果。

Input示例

Output示例

2
————————————————————————————
这道题如果单纯的在图上dp肯定会T嘛 因为n m 都是1e5的级别
那么我们可以考虑每一个不能走的格子 f[i]表示走到这个点不经过别的点的方案数
f[i]=c(x[i]+y[i]-2,x[i]-1)-sigma f[j]*c(x[i]-x[]j+y[i]-y[j],x[i]-x[j])
至于为什么要这么算呢 我们可以用总的路径减去不合法的路径 而每一条不合法的路径
就是先到一个点然后后面乱走嘛 这样就可以保证不算重了2333

#include<cstdio>

#include<cstring>

#include<algorithm>

#define LL long long

const int M=1e6+,mod=1e9+,N=1e5+;

int read(){

    int ans=,f=,c=getchar();

    while(c<''||c>''){if(c=='-') f=-; c=getchar();}

    while(c>=''&&c<=''){ans=ans*+(c-''); c=getchar();}

    return ans*f;

}

int n,m,p;

struct pos{int x,y;}q[M];

bool cmp(pos a,pos b){return a.x!=b.x?a.x<b.x:a.y<b.y;}

LL w[*N],inv[*N];

LL pmod(LL a,LL b){

    LL ans=;

    while(b){

        if(b&) ans=ans*a%mod;

        b>>=; a=a*a%mod;

    }

    return ans;

}

void prepare(){

    int mx=n+m;

    w[]=; for(int i=;i<=mx;i++) w[i]=w[i-]*i%mod;

    inv[mx]=pmod(w[mx],mod-);

    for(int i=mx;i;i--) inv[i-]=inv[i]*i%mod;

}

LL C(int n,int m){return w[n]*inv[m]%mod*inv[n-m]%mod;}

LL f[M],ans;

int main(){

    //freopen("gg.cpp","r",stdin);

    n=read(); m=read();

    p=read(); prepare();

    for(int i=;i<=p;i++) q[i].x=read(),q[i].y=read();

    std::sort(q+,q++p,cmp);

    for(int i=;i<=p;i++){

        f[i]=C(q[i].x+q[i].y-,q[i].x-);

        for(int j=;j<i;j++)

        f[i]=(f[i]-f[j]*C(q[i].x-q[j].x+q[i].y-q[j].y,q[i].x-q[j].x)%mod+mod)%mod;

    }

    ans=C(n+m-,n-);

    for(int i=;i<=p;i++) ans=(ans-f[i]*C(n-q[i].x+m-q[i].y,n-q[i].x)%mod+mod)%mod;

    printf("%lld\n",(ans+mod)%mod);

    return ;

}

巴特西

51nod 1486 大大走格子——dp

最新文章

热门文章