2016百度之星初赛（AstarRound2B）瞬间移动

【题意】点击打开链接

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

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

【AC代码】

//Cloud , you are my sunshine!
//I can&＃39;t live without you!
//You are the most beautiful girl in the world!
#include
#include
#include
#include
using namespace std;
typedef long long LL;
const int maxn&＃61;200005;
const LL mod&＃61;1000000007;
int n,m;
LL fac[maxn];
void Init(){fac[0]&＃61;1;for(int i&＃61;1; i<&＃61;maxn; i&＃43;&＃43;)fac[i]&＃61;fac[i-1]*i%mod;
}
LL pow(LL a,LL n){LL res&＃61;1,temp&＃61;a;while(n){if(n&1) res&＃61;res*temp%mod;temp&＃61;((temp%mod)*(temp%mod))%mod;n>>&＃61;1;}return res;
}
LL solve(int n,int m){if(n&＃61;&＃61;0||m&＃61;&＃61;0) return 1;return fac[n]*pow(fac[m]*fac[n-m]%mod,mod-2)%mod;//逆元
}
int main(){Init();while(~scanf("%d%d",&n,&m)){if(n>m) swap(n,m);n-&＃61;2,m-&＃61;2;
// cout<}