51nod 1119 机器人走方格 V2组合数

1119 机器人走方格 V2

基准时间限制：1 秒空间限制：131072 KB 分值: 10 难度：2级算法题

M * N的方格，一个机器人从左上走到右下，只能向右或向下走。有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10^9 + 7的结果。

Input

第1行，2个数M,N，中间用空格隔开。（2 <= m,n <= 1000000)

Output

输出走法的数量 Mod 10^9 + 7。

Input示例

2 3

Output示例

 1 #include <iostream>
 2 #include <cstdio>
 3 
 4 using namespace std;
 5 typedef long long LL;
 6 const int p = 1e9 + 7;
 7 LL quick_mod(LL a, LL b) {
 8     LL ans = 1;
 9     a %= p;
10     while(b) {
11         if(b & 1) {
12             ans = ans * a % p;
13             b--;
14         }
15         b >>= 1;
16         a = a * a % p;
17     }
18     return ans;
19 }
20 
21 LL C(LL n, LL m) {
22     if(m > n) return 0;
23     LL ans = 1;
24     for(int i=1; i<=m; i++) {
25         LL a = (n + i - m) % p;
26         LL b = i % p;
27         ans = ans * (a * quick_mod(b, p-2) % p) % p;
28     }
29     return ans;
30 }
31 LL Lucas(LL n, LL m) {
32     if(m == 0) return 1;
33     return C(n % p, m % p) * Lucas(n / p, m / p) % p;
34 }
35 int main() {
36     int k, T, n, m;
37     scanf("%d%d", &n, &m);
38     printf("%I64d
", C(n+m-2, m-1));
39     return 0;
40 }