HDU 5673 Robot
传送门：http://acm.hdu.edu.cn/showproblem.php?pid=5673
题目翻译
一个在原点的机器人，每秒钟可以向右走，原地不动，向左走（此时必须在原点右边）。请问(n)秒钟之后机器人依然在原点的方案数。
题解
很容易想到行动的时间必然是一个偶数，一半时间往右走一半时间往左走。
然后，知道了总的行动步数，这就是一个求长度位(n)的括号序列方案数的问题，直接是卡特兰数。
于是，答案等于(Ans = \sum_{i=0}^{\left \lfloor \frac{n}{2} \right \rfloor}C_{n}^{2\times i}\times Catalan\left ( i \right ))
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 |
#include<cstdio> #define LL long long #define Mod 1000000007 using namespace std; const int Maxn=1e6; LL fac[Maxn+5]; LL facNi[Maxn+5]; LL cat[Maxn+5]; inline LL powX(LL x,LL t){ LL ret=1; while(t){ if (t&1) ret=(ret*x)%Mod; t/=2LL; x=(x*x)%Mod; } return ret; } inline void init(){ fac[0]=1; for (int i=1;i<=Maxn;i++) fac[i]=(fac[i-1]*(LL)i)%Mod; for (int i=0;i<=Maxn;i++) facNi[i]=powX(fac[i],Mod-2); cat[0]=1; for (int i=1;2*i<=Maxn;i++) cat[i]=fac[i*2]*powX(fac[i]*fac[i]%Mod*(LL)(i+1)%Mod,Mod-2)%Mod; } inline void solve(){ LL Ans=0; int n=0; scanf("%d",&n); for (int i=0;i*2<=n;i++) Ans=(Ans+fac[n]*facNi[n-2*i]%Mod*facNi[2*i]%Mod*cat[i]%Mod)%Mod; printf("%lld\n",Ans); } int main(){ init(); int T=0; while(scanf("%d",&T)!=EOF){ for (int i=1;i<=T;i++) solve(); } return 0; } |
原文链接：HDU 5673 Robot
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!