有一个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示例
3 4 2
2 2
2 3
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+7,mod=1e9+7,N=1e5+7; int read(){ int ans=0,f=1,c=getchar(); while(c<'0'||c>'9'){if(c=='-') f=-1; c=getchar();} while(c>='0'&&c<='9'){ans=ans*10+(c-'0'); 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[2*N],inv[2*N]; LL pmod(LL a,LL b){ LL ans=1; while(b){ if(b&1) ans=ans*a%mod; b>>=1; a=a*a%mod; } return ans; } void prepare(){ int mx=n+m; w[0]=1; for(int i=1;i<=mx;i++) w[i]=w[i-1]*i%mod; inv[mx]=pmod(w[mx],mod-2); for(int i=mx;i;i--) inv[i-1]=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=1;i<=p;i++) q[i].x=read(),q[i].y=read(); std::sort(q+1,q+1+p,cmp); for(int i=1;i<=p;i++){ f[i]=C(q[i].x+q[i].y-2,q[i].x-1); for(int j=1;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-2,n-1); for(int i=1;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 ",(ans+mod)%mod); return 0; }