bzoj#P3305. Catalan 数
Catalan 数
题目描述
众所周知,一个长度为 的合法括号序列的方案数为 , 为 Catalan 数第 项,由简单的补集转化可以得出:
但这并不是本题要讨论的。不妨令括号序列左括号为 1
,右括号为 0
,则括号序列可映射到 01 序列上。
设所有长度为 的 01 括号序列形成的集合为 ,对于一个 01 序列 (),有其对应的系数序列 (),如下定义 为:
由上面讨论的,显然()时,。
现对于每一个 01 序列 ,有:
$$x_i=\begin{cases}1&x_i=1\\2\times \sum_{1\leq k\leq i}x_k-i&x_i=0\end{cases} $$求 的值,其中 。
输入格式
一行,一个整数 。
输出格式
一个整数表示答案。
3
15
数据规模与约定
对于 的数据,。
题目来源
By 2255。