题意

有一个n*m的点阵，初始时你在左上角，其中最下面a行和最左边b列的交点位置，也就是总共有 a∗b a ∗ b 个位置是不能走的。你每次只能向下或向右走问你走到点阵的右下角有多少种不同的方案。 n,m<=100000

分析

直接枚举从哪一个点跨出左上角大小为 (n−a)∗b ( n − a ) ∗ b 的矩形即可。

代码

#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> using namespace std; typedef long long LL; const int N=200005; const int MOD=1000000007; int n,m,a,b,jc[N],ny[N]; int C(int n,int m) { return (LL)jc[n]*ny[m]%MOD*ny[n-m]%MOD; } int main() { scanf("%d%d%d%d",&n,&m,&a,&b); jc[0]=jc[1]=ny[0]=ny[1]=1; for (int i=2;i<=n+m;i++) jc[i]=(LL)jc[i-1]*i%MOD,ny[i]=(LL)(MOD-MOD/i)*ny[MOD%i]%MOD; for (int i=2;i<=n+m;i++) ny[i]=(LL)ny[i-1]*ny[i]%MOD; int ans=0; for (int i=1;i<=n-a;i++) (ans+=(LL)C(i+b-2,b-1)*C(n-i+m-b-1,n-i)%MOD)%=MOD; printf("%d",ans); return 0; }