首页 > 代码库 > 1120 机器人走方格 V3

1120 机器人走方格 V3

2024-08-11 01:20:17   218人阅读

 

1120 机器人走方格 V3
基准时间限制：1 秒 空间限制：131072 KB

 

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

 

Input
输入一个数N(2 <= N <= 10^9)。
Output
输出走法的数量 Mod 10007。
Input示例
4
Output示例
10

思路：这个在对角线的上方，就可以转换为，火车进站的问题，火车进站出来的肯定要小于等于进站的，那么也就相当于y>=x;那么就是卡特兰数，然后因为严格上方，所以我们要求的是F（n-1）卡特兰数，然后我们用lucas来求组合数取模。

 1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<math.h> 7 using namespace std; 8 const int mod = 10007; 9 typedef long long LL;10 LL N[10008];11 LL quick(LL n,LL m);12 LL lucas(LL n,LL m);13 int main(void)14 {15     N[0] = 1;16     int i,j;17     for(i = 1; i <= 10007; i++)18         N[i] = N[i-1]*(LL)i%mod;19     LL n;20     scanf("%lld",&n);n--;21     if(n==0)printf("1\n");22     else23     {LL ask = lucas(2*n,n) - lucas(2*n,n-1);24     ask = ask%mod + mod;25     printf("%lld\n",2*ask%mod);}26     return 0;27 }28 LL lucas(LL n,LL m)29 {30     if(m == 0)return 1;31     LL x = n%mod;32     LL y = m%mod;33     if(y > x)34         return 0;35     LL ni = N[x-y]*N[y]%mod;36     ni =quick(ni,mod-2);37     ni = ni*N[x]%mod;38     return ni*lucas(n/mod,m/mod);39 }40 LL quick(LL n,LL m)41 {42     LL ans = 1;43     n %= mod;44     while(m)45     {46         if(m&1)47             ans = ans*n%mod;48         n = n*n%mod;49         m>>=1;50     }51     return ans;52 }

 

1120 机器人走方格 V3


联系
我们