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

收藏

关注

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

Input

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

Output

输出走法的数量。

Input示例

2 3

Output示例

3

1     #include
       
         2     #include
        
          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<
        
       

 

　　这道题要注意的是： 当单纯的用组合累乘的话 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 ）

 

基准时间限制：1 秒 空间限制：131072 KB 分值: 80

收藏

关注

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

 

Input

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

Output

输出走法的数量 Mod 10007。

Input示例

4

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
         
           8     #include
          
            9     #include
           
            10     #include
            
             11     #include
             
              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
              
>= 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<