【数学】卡特兰数

用来练习卡特兰数。如果有很好的题，且题单上没有的话，可以私信[ダ月](https://www.luogu.com.cn/user/511271)。 这是 [OI-Wiki](https://oi-wiki.org/math/combinatorics/catalan/) 内对应卡特兰数的链接。 **部分题请不要当多倍经验做**。 --- 卡特兰数用三种表达式，记 $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$ 不是一个质数。| --- ### 多倍经验： 有些题有多倍经验，但是不放在这个题单内，放在这个[剪切板](https://www.luogu.com.cn/paste/rz4e0khe)内。