机器人走方格 V2
M * N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。
Input
第1行，2个数M,N，中间用空格隔开。（2 <= m,n <= 1000000)
Output
输出走法的数量 Mod 10^9 + 7。
Sample Input
2 3
Sample Output
3 解析 我们可以推出（i行j列的走法）dp[i][j]=dp[i][j-1]+dp[i-1][j],又可以推出（i-j行j列的走法）p[i][j] = dp[i-j][j]=dp[i-j-1][j]+dp[i-j][j-1]=p[i-1][j]+r[i-1][j-1]
p[i][j]=p[i-1][j]+p[i-1][j-1] 即组合数公式 C(n-1+m-1,n-1) 数据过大要求取模 除法不能取模 要求逆元 完成解答。
#include <iostream>
#include <cstdlib>
#include <cstdio>
#include <cstring>
#include <string>
#include <algorithm>
#include <set>
#include <queue> using namespace std; const int mod = ;
const int MAXN = ;
long long f[MAXN * + ];
int n,m; void init()
{
f[] = ;
f[] = ;
for(int i = ; i <= ; i++)
f[i] = (f[i - ] * i) % mod;
}
long long pow(long long n,long long m)
{
long long ans = ;
while(m > )
{
if(m & )ans = (ans * n) % mod;
m = m >> ;
n = (n * n) % mod;
}
return ans;
}
long long computer()
{
long long ans = f[n - + m - ];
ans = (ans * pow(f[n-],mod - )) % mod;
ans = (ans * pow(f[m - ] ,mod - )) % mod;
return ans;
}
int main()
{
init();
while(~scanf("%d%d",&n,&m))
{
cout<<computer()<<endl;
}
return ;
}