有一个h行w列的棋盘，里面有一些格子是不能走的，现在要求从左上角(1,1)走到右下角(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取余的结果。
组合数学。设ans[i]表示从(1,1)走到第i个不能走的格子，且中间不经过其他障碍格的方案数。（把(h,w)也当成障碍格）
ans[i]= C( X[i]-1+Y[i]-1 , X[i]-1 ) - sum{ ans[j]*C( X[i]-X[j]+Y[i]-Y[j] , X[i]-X[j] ) }，点j在点i的左上方（包括左方或上方）。
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<algorithm> 5 #include<queue> 6 #define ll long long 7 #define ull unsigned long long 8 #define ui usigned int 9 #define d double 10 #define ld long double 11 const int maxn=2023,modd=1000000007; 12 struct zs{int x,y;}a[maxn]; 13 int jc[200233],ny[200233],ans[maxn]; 14 int i,j,k,n,m; 15 16 int ra,fh;char rx; 17 inline int read(){ 18 rx=getchar(),ra=0,fh=1; 19 while(rx<'0'&&rx!='-')rx=getchar(); 20 if(rx=='-')fh=-1,rx=getchar(); 21 while(rx>='0')ra=ra*10+rx-48,rx=getchar();return ra*fh; 22 } 23 24 inline int getc(int n,int m){ 25 return 1ll*jc[n]*ny[n-m]%modd*ny[m]%modd; 26 } 27 inline int get(int x,int y){ 28 return getc(x+y,y); 29 } 30 inline int poi(int a,int b){ 31 int c=1; 32 while(b){ 33 if(b&1)c=1ll*c*a%modd; 34 a=1ll*a*a%modd,b>>=1; 35 }return c; 36 } 37 bool operator <(zs a,zs b){return a.x<b.x||(a.x==b.x&&a.y<b.y);} 38 inline void UPD(int &x){if(x<0)x+=modd;} 39 int main(){ 40 n=read(),m=read();int num=read();register int i,j; 41 for(i=jc[0]=ny[0]=1;i<=n+m;i++)jc[i]=1ll*jc[i-1]*i%modd,ny[i]=poi(jc[i],modd-2); 42 // for(i=1;i<=n||i<=m;i++)for(j=1;j<=i;j++)printf("%d %d c:%d ",i,j,getc(i,j)); 43 for(i=1;i<=num;i++)a[i].x=read()-1,a[i].y=read()-1; 44 a[++num]=(zs){n-1,m-1}; 45 std::sort(a+1,a+1+num); 46 for(i=1;i<=num;i++){ 47 ans[i]=get(a[i].x,a[i].y);//printf("(%d,%d) %d ",a[i].x,a[i].y,ans[i]); 48 for(j=1;j<i;j++)if(a[j].y<=a[i].y) 49 UPD(ans[i]-=1ll*ans[j]*get(a[i].x-a[j].x,a[i].y-a[j].y)%modd); 50 } 51 printf("%d ",ans[num]); 52 }