bzoj#P3305. Catalan 数

Catalan 数

题目描述

众所周知,一个长度为 2n2n 的合法括号序列的方案数为 CnC_nCnC_n 为 Catalan 数第 nn 项,由简单的补集转化可以得出:

Cn=1n+1(2nn)C_n=\dfrac{1}{n+1} \dbinom{2n}n

但这并不是本题要讨论的。不妨令括号序列左括号为 1,右括号为 0,则括号序列可映射到 01 序列上。

设所有长度为 2n2n 的 01 括号序列形成的集合为 GnG_n,对于一个 01 序列 aia_i1i2n1\leq i\leq 2n),有其对应的系数序列 aia_i^\prime1i2n1\leq i\leq 2n),如下定义 FnF_n 为:

Fn=xGni=12nxiF_n=\sum_{x\in G_n} \prod_{i=1}^{2n} x_i^\prime

由上面讨论的,显然ai=1a_i^\prime=11i2n1\leq i\leq 2n)时,Fn=CnF_n=C_n

现对于每一个 01 序列 xix_i,有:

$$x_i=\begin{cases}1&x_i=1\\2\times \sum_{1\leq k\leq i}x_k-i&x_i=0\end{cases} $$

FnmodpF_n\bmod p 的值,其中 p=109+9p=10^9+9

输入格式

一行,一个整数 nn

输出格式

一个整数表示答案。

3
15

数据规模与约定

对于 100%100\% 的数据,1n1071\leq n\leq 10^7

题目来源

By 2255。