机器人走方格 V3

1120 . 机器人走方格 V3

基准时间限制：1 秒空间限制：65536 KB 分值: 160

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

Input

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

Output

输出走法的数量 Mod 10007。

Input 示例

Output 示例

10

思路:实际是本质就是，n个0，n个1，序列中1的个数小于等于0.
和string是同一类型题。c(n+m,n)-c(n+m,n-1);
这题需要*2；
由于mod = 10007；

 1 /**C(n+m,n)-C(n+m,n-1)**/
 2 #include<iostream>
 3 #include<stdio.h>
 4 #include<cstring>
 5 #include<cstdlib>
 6 using namespace std;
 7 typedef __int64 LL;
 8 
 9 const LL p = 10007;
10 LL dp[10008];
11 void init()
12 {
13     int i;
14     dp[0]=1;
15     for(i=1;i<=10007;i++)
16         dp[i]=(dp[i-1]*i)%p;
17 }
18 LL pow_mod(LL a,LL n)
19 {
20     LL ans=1;
21     a=a%p;
22     while(n)
23     {
24         if(n&1) ans=(ans*a)%p;
25         n=n>>1;
26         a=(a*a)%p;
27     }
28     return ans;
29 }
30 LL C(LL n,LL m)
31 {
32     if(n<m)return 0;
33     if(m>n-m) m=n-m;
34     LL sum1=dp[n];
35     LL sum2=(dp[m]*dp[n-m])%p;
36     sum1 = (sum1*pow_mod(sum2,p-2))%p;
37     return sum1;
38 }
39 LL Lucas(LL n,LL m)
40 {
41     LL ans=1;
42     while(n&&m&&ans)
43     {
44         ans=(ans*C(n%p,m%p))%p;
45         n=n/p;
46         m=m/p;
47     }
48     return ans;
49 }
50 int main()
51 {
52     init();
53     LL n;
54     while(scanf("%I64d",&n)>0)
55     {
56         n=n-1;
57         LL ans=Lucas(n+n,n);
58         LL cur=Lucas(n+n,n-1);
59         ans=ans-cur;
60         if(ans<0) ans=ans+p;
61         ans=(ans*2)%p;
62         printf("%I64d
",ans);
63     }
64     return 0;
65 }

对比

Garden visiting

http://acm-hit.sunner.cn/judge/show.php?Proid=2813

C(n+m-2,n-1)%p;