从（1,1）到（n,m），每次向右或向下走一步，,不能经过（x,y），求走的方案数取模。
可以经过（x,y）则相当于m+n步里面选n步必须向下走，方案数为
C((m−1)+(n−1)，n−1)
再考虑其中经过（x,y）的方案数，也就是（1,1）到（x,y）的方案乘上（x,y）到（n,m）的方案，为
C((x−1)+(y−1),x−1)×C((n−x)+(m−y),n−x)
于是答案就是下式取模
C(m+n−2，n−1)−C(x+y−2,x−1)×C(n−x+m−y,n−x)
m和n大到10的五次方，而组合数要用除法，所以要用费马小定理来求逆元。简单的说就是
C(n,m)%M=n!%M×(m!)−1%M×[(n−m)!]−1%M
而逆元用费马小定理和快速幂来算
(m!)−1=qpow(m!,M−2)
最后减法取模记得要再加M再取一次模。
#include<bits/stdc++.h> #define N 200005 #define M 1000000007 #define ll long long using namespace std; ll n,m,t,x,y,fac[N]= {1}; ll qpow(ll a,ll b) { ll ans=1; ll k=a; while(b) { if(b&1)ans=ans*k%M; k=k*k%M; b>>=1; } return ans; } ll C(ll n,ll m) { if(m>n)return 0; return fac[n]*qpow(fac[m],M-2)%M*qpow(fac[n-m],M-2)%M; } int main() { for(int i=1; i<N; i++)fac[i]=fac[i-1]*i%M; scanf("%d",&t); while(t--) { scanf("%d%d%d%d",&n,&m,&x,&y); printf("%lld\n",((C(n+m-2,n-1)-C(x+y-2,x-1)*C(n-x+m-y,n-x)%M+M)%M)); } return 0; }