首页 > 代码库 > Robot(hdu5673)
Robot(hdu5673)
Robot
Accepts: 92
Time Limit: 12000/6000 MS (Java/Others)
Memory Limit: 65536/65536 K (Java/Others)
问题描述
有一个机器人位于坐标原点上。每秒钟机器人都可以向右移到一个单位距离,或者在原地不动。如果机器人的当前位置在原点右侧,它同样可以向左移动单位距离。一系列的移动(左移,右移,原地不动)定义为一个路径。问有多少种不同的路径,使得nnn秒后机器人仍然位于坐标原点?答案可能很大,只需输出答案对1,000,000,0071,000,000,0071,000,000,007的模。
输入描述
输入包含多组数据. 第一行有一个整数T(1≤T≤100)T (1\leq T\leq 100)T(1≤T≤100), 表示测试数据的组数. 对于每组数据:输入一个整数 n(1≤n≤1,000,000)n (1\leq n\leq 1,000,000)n(1≤n≤1,000,000)。
输出描述
对于每组数据,输出一个整数
输入样例
3124
输出样例
129
思路:默慈金数
在一个网格上,若限定每步只能向右移动一格,可以右上,右下,
横向,向右,并禁止移动到以下的地方,则以这种走法移动步从到的可能形成的路径的总数
为的默慈金数。如下图示
默慈金数满足如下递推式:
可以将点的过程想象成上图,那么就是一个很裸的默慈金数;
1 #include<stdio.h> 2 #include<algorithm> 3 #include<iostream> 4 #include<string.h> 5 #include<queue> 6 #include<set> 7 #include<math.h> 8 #include<map> 9 const int N =1e9+7;10 using namespace std;11 typedef long long LL;12 LL quick(LL n,LL m,LL mod);13 LL M[1000005];14 int main(void)15 {16 M[1] = 1;M[0] = 1;int i;17 for(i = 2;i <= 1000000;i++)18 {19 LL x = (2*i+1)*M[i-1]%N;20 LL y = (3*i-3)*M[i-2]%N;21 x = (x+y)%N;22 y = i+2;23 LL ni = quick(y,N-2,N);24 //printf("%lld\n",ni);25 M[i] = x*ni%N;26 }27 int T;28 scanf("%d",&T);29 while(T--)30 {31 int n;32 scanf("%d",&n);33 printf("%lld\n",M[n]);34 }35 return 0;36 }37 LL quick(LL n,LL m,LL mod)38 {39 n%=mod;40 LL ask = 1;41 while(m)42 {43 if(m&1)44 ask = ask*n%mod;45 n = n*n%mod;46 m>>=1;47 }48 return ask;49 }
Robot(hdu5673)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。