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 ))

代码