机器人走方格 V3

1120 . 机器人走方格 V3
 
基准时间限制：1 秒 空间限制：65536 KB 分值: 160
N * N的方格，从左上到右下画一条线。一个机器人从左上走到右下，只能向右或向下走。并要求只能在这条线的上面或下面走，不能穿越这条线，有多少种不同的走法？由于方法数量可能很大，只需要输出Mod 10007的结果。

 

Input

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

Output

输出走法的数量 Mod 10007。

Input 示例

4

Output 示例

10

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

 /**C(n+m,n)-C(n+m,n-1)**/

 #include<iostream>

 #include<stdio.h>

 #include<cstring>

 #include<cstdlib>

 using namespace std;

 typedef __int64 LL;

 const LL p = ;

 LL dp[];

 void init()

 {

     int i;

     dp[]=;

     for(i=;i<=;i++)

         dp[i]=(dp[i-]*i)%p;

 }

 LL pow_mod(LL a,LL n)

 {

     LL ans=;

     a=a%p;

     while(n)

     {

         if(n&) ans=(ans*a)%p;

         n=n>>;

         a=(a*a)%p;

     }

     return ans;

 }

 LL C(LL n,LL m)

 {

     if(n<m)return ;

     if(m>n-m) m=n-m;

     LL sum1=dp[n];

     LL sum2=(dp[m]*dp[n-m])%p;

     sum1 = (sum1*pow_mod(sum2,p-))%p;

     return sum1;

 }

 LL Lucas(LL n,LL m)

 {

     LL ans=;

     while(n&&m&&ans)

     {

         ans=(ans*C(n%p,m%p))%p;

         n=n/p;

         m=m/p;

     }

     return ans;

 }

 int main()

 {

     init();

     LL n;

     while(scanf("%I64d",&n)>)

     {

         n=n-;

         LL ans=Lucas(n+n,n);

         LL cur=Lucas(n+n,n-);

         ans=ans-cur;

         if(ans<) ans=ans+p;

         ans=(ans*)%p;

         printf("%I64d\n",ans);

     }

     return ;

 }

对比

Garden visiting

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

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

机器人走方格 V3的相关教程结束。