【数学】卡特兰数

用来练习卡特兰数。如果有很好的题，且题单上没有的话，可以私信ダ月。

这是 OI-Wiki 内对应卡特兰数的链接。

部分题请不要当多倍经验做。

卡特兰数用三种表达式，记 H 为卡特兰数的数列，H_n 为这个数列的第 n 项。共有四种表达式：

(1)\begin{aligned}H_{n}=\sum_{i=0}^{n-1}H_iH_{n-i-1}\end{aligned},H_0=1（定义式）

(2)H_n=C_{2n}^{n}-C_{2n}^{n-1}；

(3)H_n=\frac{1}{n+1}C_{2n}^{n};

(4)\begin{aligned}&H_{n}=\frac{4n-2}{n+1}H_{n-1},&n\ge1\\&H_n=1，&n=0 &\end{aligned}

(1) 存在两种操作 1,2，要求每种操作各进行 n 次，要求在任意一个时刻，操作 1 的次数小于等于操作 2 的次数。完成这两种操作的方案数就是卡特兰数。

根据这个意义，可以依次做以下题目：P1722，P1044，P1754，P3978，AT_abc205_e，P3200，P5014，AT_arc145_c，CF1204E。

题号	简要说明
P1722	裸卡特兰数的题，黑子和红子之间的关系已经很明确了。（因为 n\le100 且模数为 100，就直接按定义式来吧。）
P1044	尝试将出入栈两种操作建立起联系。
P1754	建立起 50 块与 100 块之间的关系。
P1641	不降路径的变形之一，联系上方表达式 (2) 的推导过程。
AT_abc205_e	不降路径的变形之二。
P3200	有一点小思维，可能对 1\sim2n 的处理要换个角度。不过真正有意思的是那个取模过程。
P5014	题意需要转换，有一点思维含量（后面的是提示）尝试跟 P1641 和 P3200 建立起联系。
AT_arc145_c	想一想最大值的时候的构造方式，来联系一下卡特兰数的括号匹配。
CF1204E	括号匹配模型的扩展。

(2) 一种操作操作 n 次后完后的元素没有交集的方案数。

可以依次做以下题目：P1375，P1976。

题号	简要说明
P1375	连线是操作，两连线的交点定义为操作的交集。
P1976	类似 P1375。（注意模数）

(3) 根据打表或者 dp 方程进行观察。

可以依次做以下试题：P2532，UVA10303，P7118，P3978。

题号	简要说明
P2532	建议先想出 dp 的转移方程。需要高精度。
UVA10303	想一想 n 个结点的树有多少中形态。需要高精度。
P1984	观察 dp 式子，能看出点前面的模型。
P7118	可以在 UVA10303 的基础上想这道题。
P3978	（~~这是传说中的结论题~~）想一想叶子结点数和树的形态数的关系。

综合的题会比较有趣。

可以依次做以下题目：P4769，CF896D。

题号	简要说明
P4769	这题有点难度，可以先想想不受字典序限制时的做法，然后尝试从跟上面的题建立起联系。
CF896D	跟上方某题很像，难度评黑有点虚高，可以用来练习推式子。有意思的是模数 p 不是一个质数。

有些题有多倍经验，但是不放在这个题单内，放在这个剪切板内。