51_1118、51_1120 机器人走方格（组合+乘法逆元+卡特兰数+卢卡斯定理）

基准时间限制：1 秒空间限制：131072 KB 分值: 0 难度：基础题

关注

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

Input

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

Output

输出走法的数量。

Input示例

2 3

Output示例

 1     #include<iostream>
 2     #include<cstdio>
 3     using namespace std;
 4     typedef long long LL;
 5     
 6     const LL mod = 1e9 + 7;
 7     
 8     void ex_gcd(LL a, LL b, LL &d, LL &x, LL &y){
 9         if(b==0){
10             x =1; y=0 ; d = a;
11             return ;
12         }
13         ex_gcd(b, a%b, d, y, x);
14         y -= x*(a/b);
15     } 
16     
17     //乘法逆元 ax = 1(mod m) 
18     LL inverse(LL a, LL m){
19         LL x, y, d;
20         ex_gcd( a, m, d, x, y);    
21         if(d!=1)    return 0;
22         return (x%m + m)%m;
23     }
24 
25     
26     LL comb(LL m, LL n){
27         LL t1 =1, t2=1;
28         for(LL i = n-m+1 ; i<=n ; ++i)    t1 = t1*i%mod;
29         for(LL i = 1 ; i<=m ; ++i)    t2 = t2*i%mod;
30         return t1*inverse(t2, mod)%mod;
31     } 
32     
33     int main(){
34         int a, b;
35         cin>> a >> b;
36         cout<<comb(max(a-1, b-1), a+b-2)%mod<<endl;
37     }

　　这道题要注意的是：当单纯的用组合累乘的话 1000！即使long long也会溢出，所以只能乘一下， mod一下，但是这样分子分母算出来后，分子/分母肯定就已经不是答案（因为分子%mod / 分母%mod ！= ans%mod )，此时，就要用到乘法逆元。

　　ax ≡ 1(mod m) , 则 t1 * x * t2 mod m = t1 -> t1 / t2 = t1* x mod m （将除法转换成乘法，保证 t1/t2 的结果为 ans%mod ）

1120 机器人走方格 V3

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

关注

N * N的方格，从左上到右下画一条线。一个机器人从左上走到右下，只能向右或向下走。并要求只能在这条线的上面或下面走，不能穿越这条线，有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10007的结果。

Input

输入一个数N(2 <= N <= 10^9)。

Output

输出走法的数量 Mod 10007。

Input示例

Output示例

10

这道题用到了卡特兰数（详情见下篇转的博客），然后外加求大组合数取模的卢卡斯定理（这个定理实在太好用了，妈妈再也不用担心组合数）！

首先给出这个Lucas定理：

 A、B是非负整数，p是质数。AB写成p进制：A=a[n]a[n-1]...a[0]，B=b[n]b[n-1]...b[0]。

则组合数C(A,B)与C(a[n],b[n])*C(a[n-1],b[n-1])*...*C(a[0],b[0])  modp同余

即：Lucas(n,m,p)=c(n%p,m%p)*Lucas(n/p,m/p,p)

粗略的方便理解的方法：以求解n! % p为例，把n分段，每p个一段，每一段求的结果是一样的。但是需要单独处理每一段的末尾p, 2p, ...，把p提取出来
，会发现剩下的数正好又是(n / p)!，相当于划归成了一个子问题，这样递归求解即可。

 1 /*
 2     机器人走方格V3
 3     时间：2016年4月20日00:05:22
 4     作者：W2W
 5 */ 
 6 
 7     #include<iostream>
 8     #include<cstdio>
 9     #include<iomanip>
10     #include<string>
11     #include<cstring>
12     using namespace std;
13     typedef long long LL;
14     
15     const LL mod = 10007;
16     const LL maxn = 50001;
17     
18     LL fac[maxn];
19     void init(LL p){
20         memset(fac, 0, sizeof(fac));
21         fac[1] = 1;
22         for(int i=2; i<p ; ++i){
23             fac[i] = fac[i-1]*i%p;
24         }
25     }
26     
27     LL qsm(LL a, LL n, LL p){
28         LL res = 1;
29         while(n){
30             if(n&1)    res = (res*a)%p;
31             a = (a*a)%p;
32             n >>= 1;
33         }
34         return res;
35     }
36     
37     void ex_gcd(LL a, LL b, LL& d, LL& x, LL& y){
38         if(b==0){
39             x = 1; y = 0 ; d = a;
40             return ;
41         }
42         ex_gcd(b, a%b, d, y, x);
43         y -= x*(a/b);
44     } 
45     
46     LL reverse(LL a, LL m){
47         LL x, y, d;
48         ex_gcd(a, m, d, x, y);
49         if(d==1)    return (x%m + m)%m;
50         else return 0;
51     }
52     //卢卡斯定理  C(m, n)%p  
53     LL Lucas(LL m, LL n, LL p){
54         LL res = 1;
55         while(n && m){
56             LL n1 = n%p, m1 = m%p;
57             //费马小定理求逆元 
58             res = res* fac[n1]* qsm(fac[m1]*fac[n1-m1]%p, p-2, p)%p;
59             //扩展欧几里得求逆元 
60             //res = res* fac[n1]* reverse(fac[m1],p)* reverse(fac[n1-m1],p)%p;
61             n /= p;
62             m /= p;
63         }
64         return (res%p + p)%p;
65     }
66     
67     int main(){
68         LL n;
69         init(mod);
70         cin>>n;
71         n--;
72         //卡特兰数  C(n, 2*n)/(n+1) 
73         cout<<2*Lucas(n, 2*n, mod)*reverse(n+1, mod)%mod<<endl;
74         return 0;
75     }