题目链接：http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1627
有一个无限大的矩形，初始时你在左上角（即第一行第一列），每次你都可以选择一个右下方格子，并瞬移过去（如从下图中的红色格子能直接瞬移到蓝色格子），求到第n行第m列的格子有几种方案，答案对1000000007取模。
Input
单组测试数据。
两个整数n,m（2<=n,m<=100000）
Output
一个整数表示答案。
Input示例
4 5
Output示例
10
题解：
1.如果去除掉起点和终点，那么就是对中间的矩形进行统计。则首先 n -= 2， m -= 2。
2. 可知里边的矩形最多只能有 min(n,m)个足迹，假设m = min(n,m)，即最多只能有m个足迹。
3.根据以上两点，可以枚举矩形里足迹的个数i，然后再为这i个足迹分配横、纵坐标，总共有 C(n,i)*C(m,i)种情况，则最终答案为：∑C(n,i)*C(m,i) ， 0<=i<=m 。
代码如下：
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <string>
#include <set>
using namespace std;
typedef long long LL;
const int INF = 2e9;
const LL LNF = 9e18;
const int MOD = 1e9+;
const int MAXM = 1e5+;
const int MAXN = 2e5+; LL qpow(LL x, LL y)
{
LL s = ;
while(y)
{
if(y&) s = (s*x)%MOD;
x = (x*x)%MOD;
y >>= ;
}
return s;
} LL A[MAXN], inv[MAXN];
LL C(LL n, LL m)
{
if(n<m) return ;
return (((A[n]*inv[n-m])%MOD)*inv[m])%MOD;
} void init()
{
A[] = inv[] = ;
for(int i = ; i<MAXN; i++)
{
A[i] = i*A[i-]%MOD;
inv[i] = qpow(A[i], MOD-);
}
} int main()
{
init();
LL n, m;
while(scanf("%lld%lld",&n,&m)!=EOF)
{
n -= ; m -= ; //去掉起始点和终点，只对里边的矩形进行统计
if(n<m) swap(n,m);
LL ans = ;
for(int i = ; i<=m; i++) //里边的矩形最多只能有min(n,m)个“足迹”,即最多只能走min(n,m)+1步
ans = (ans+C(m,i)*C(n,i)%MOD)%MOD; //如果里边有i个足迹，则为这i个足迹选择横坐标、纵坐标
printf("%lld\n", ans);
}
}