題面描述

給定一個的棋盤造虏，棋盤上只有個格子是黑色的，其他格子都是白色的茁计。在棋盤左上角有一個卒击敌，每一步可以向右或者向下移動一格，并且不能移動到黑色格子中焕妙。求這個卒從左上角移動到右下角蒋伦，一共有多少種可能的路線。

輸入格式

第行：個正整數(shù)焚鹊。
接下來n行痕届，第行包含兩個整數(shù)，即黑色格子的坐標

輸出格式

輸出一個整數(shù)末患，即總的方案數(shù)研叫。

樣例

樣例輸入

100 100 3
15 16
16 15
99 88

樣例輸出

545732279

題解

題目的數(shù)據(jù)范圍肯定是不能直接寫暴力的(即使是記憶化搜索也會導致空間超限)。因此我們考慮先用組合計數(shù)的方式求出總的方案數(shù)璧针，再減去不合法的方案數(shù)嚷炉。
在一個正方形矩陣中，我們?nèi)粝胗米钚〉牟綌?shù)從走到探橱，一共只需要走x+y步申屹，而決定方案數(shù)的僅僅是我們選擇第步是向坐標移動還是向坐標移動，因此可知總方案數(shù)為
我們再減去其中加上所有會到達黑色方塊的方案數(shù)即可隧膏。

#include<bits/stdc++.h>
#define int long long
#define mod 1000000007
#define maxn 200011
using namespace std;
inline char get(){
    static char buf[30000],*p1=buf,*p2=buf;
    return p1==p2 && (p2=(p1=buf)+fread(buf,1,30000,stdin),p1==p2)?EOF:*p1++;
}
inline int read(){
    register char c=get();register int f=1,_=0;
    while(c>'9' || c<'0')f=(c=='-')?-1:1,c=get();
    while(c<='9' && c>='0')_=(_<<3)+(_<<1)+(c^48),c=get();
    return _*f;
}
struct edge{
    int x,y;
}a[maxn];
bool cmp(edge x1,edge x2){
    if(x1.x==x2.x) return x1.y<x2.y;
    return x1.x<x2.x;
}
int inv[maxn],fac[maxn];
int ksm(int a,int b){
    int ans=1;
    while(b){
        if(b&1) ans*=a,ans%=mod;
        a*=a,a%=mod;
        b>>=1;
    }return ans%mod;
}
inline void init(){
    inv[0]=1,fac[0]=1;
    for(register int i=1;i<maxn;i++){
        fac[i]=(fac[i-1]*i)%mod;
        inv[i]=ksm(fac[i],mod-2);
    }
}
int n,m,k;
int C(int m,int n){
    if(n==0)return 1;
    return (fac[m]*((inv[n]*inv[m-n])%mod))%mod;
}
int f[maxn];
signed main(){
    //freopen("1.txt","r",stdin);
    init();
    n=read(),m=read(),k=read();
    for(register int i=1;i<=k;i++)a[i].x=read(),a[i].y=read();
    sort(a+1,a+k+1,cmp);
    k++;
    a[k].x=n,a[k].y=m;
    for(register int i=1;i<=k;i++){
        f[i]=C(a[i].x+a[i].y-2,a[i].x-1)%mod;
        for(register int j=1;j<i;j++){
            if(a[j].x>a[i].x||a[j].y>a[i].y) continue;
            f[i]-=f[j]*C(a[i].x-a[j].x+a[i].y-a[j].y,a[i].x-a[j].x);
            f[i]=((f[i]%mod)+mod)%mod;
        }
    }
    cout<<(f[k]%mod+mod)%mod;
}