【题意】点击打开链接

【分析&解题思路】除去起点(1,1)和终点(n,m)已经固定,中间能经过的是一个(n-2)*(m-2)的矩阵然后我们可以在这个矩阵里取0个(就是直接从起点跳到终点)、1个、2个……min(n,m)-2个间接点而对于取i个间接点,其实就是确定这i个间接点行数与列数有多少种取法于是,我们得到了组合数公式(假设n<m,此题n,m和m,n结果是一样的,过我们可以交换n,m实现n<m)

为了让式子看起来更简洁,对于输入的n与m,我们预处理-2,即n-=2,m-=2,这样上述式子就变成了化简。

【AC代码】

//Cloud , you are my sunshine!
//I can't live without you!
//You are the most beautiful girl in the world!
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int maxn=200005;
const LL mod=1000000007;
int n,m;
LL fac[maxn];
void Init(){
    fac[0]=1;
    for(int i=1; i<=maxn; i++)
        fac[i]=fac[i-1]*i%mod;
}
LL pow(LL a,LL n){
    LL res=1,temp=a;
    while(n){
        if(n&1) res=res*temp%mod;
        temp=((temp%mod)*(temp%mod))%mod;
        n>>=1;
    }
    return res;
}
LL solve(int n,int m){
    if(n==0||m==0) return 1;
    return fac[n]*pow(fac[m]*fac[n-m]%mod,mod-2)%mod;<span style="font-family:Courier New;">//逆元</span>
}
int main(){
    Init();
    while(~scanf("%d%d",&n,&m)){
        if(n>m) swap(n,m);
        n-=2,m-=2;
//        cout<<n<<" "<<m<<endl;
        LL ans=solve(n+m,n);
        printf("%I64d\n",ans);
    }
    return 0;
}