专栏文章

[学习笔记25] 卡特兰数学习笔记

IImaginative
个人记录参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@min5o3od
此快照首次捕获于
2025/12/01 20:58
3 个月前
此快照最后确认于
2025/12/01 20:58
3 个月前
查看原文
是一个组合数学的数列，通项公式如下 Cn=1n+1(2nn)C_n=\frac{1}{n+1}\begin{pmatrix}2n\\n\end{pmatrix} 递推公式如下 Cn=∑i=0n−1Ci×Cn−i−1C_n=\sum_{i=0}^{n-1}C_i\times C_{n-i-1} 特别的 C0=1C_0=1
卡特兰数一般用来解决以下问题:
  • 括号匹配的个数
  • 栈操作序列（push 和 pop）的可能数目
  • 二叉树种类计数
  • 凸多边形三角划分
  • 在网格图中从 (0,0)(0,0) 到 (n,n)(n,n) 不越过对角线的路径数
你要问这个数有什么具体意义吗，我感觉没啥意义吧，就比如斐波那契数列也没有什么很特别的意义。它只是适合解决上面这一类问题。
现在来两个经典例子。

括号序列

问题:求长度为 nn 对(不是 nn 个)括号的合法序列数。
求解思路:
  1. 任何一个非空的合法括号序列，第一个字符一定是左括号(
  2. 这个左括号一定对应一个右括号 )，它们之间是一个合法的括号序列，右边也是一个合法的括号序列
即形如(A)B(A)B
那么A的方案数为 Ci−1C_{i-1} B的方案数为 Cn−i−1C_{n-i-1}
总方案数显然是卡特兰数

路径计数

问题:在网格图中从 (0,0)(0,0) 到 (n,n)(n,n) 不越过对角线的路径数。
做法很多，这里介绍反射变换。
不考虑限制，总路线显然是 (2nn)\begin{pmatrix}2n\\n\end{pmatrix}
考虑除去非法部分，将这条路径在第一次碰到 y=x+1y=x+1 之后的部分，关于直线 y=x+1y=x+1 作对称。
终点变为 (n−1,n+1)(n-1,n+1)
容易想到 (0,0)(0,0) 到 (n−1,n+1)(n-1,n+1) 的总路径数反射回去一定是非法的(也容易想到所有非法的一定能反射，不懂的可以手画个图)
这种方案数是 (2nn−1)\begin{pmatrix}2n\\n-1\end{pmatrix}
两者相减，得
(2nn)−(2nn−1)\begin{pmatrix}2n\\n\end{pmatrix}-\begin{pmatrix}2n\\n-1\end{pmatrix}
=(2n)!n!×n!−(nn+1×(2n)!n!×n!)=\frac{(2n)!}{n!\times n!}- (\frac{n}{n+1}\times \frac{(2n)!}{{n!} \times n!})
=1n+1(2nn)=\frac{1}{n+1}\begin{pmatrix}2n\\n\end{pmatrix}
显然是卡特兰数通项公式。

例题

A.消失的序列

机房学生吊打标解时刻%%%
当出题人还在用卡特兰数卷积，正解还在写极为复杂的分类讨论dp，某位大神则将其变为括号序列问题吊打标程，成为了今日的神话。
题意: 某个神人对一个数列有一种排序方式，它的排序方式有以下两种:
  1. 从弹出数列第一个数压入栈中
  2. 从栈顶弹出一个数(到已弹出数列的最后)
这个神人原本有一个数列，而且它记得它的数列可以通过这种方式将数列排序成有序的(小到大)。但是它却不记得原本数列是什么了，只记得一个位置 pospos 填的是 valval ，问你它原本的数列有多少种可能。
(这神人记性真好)
这个数列是一个 [1,n][1,n] 的排列，每次给定n,pos,valn,pos,val
n≤106n \le 10^6
神仙做法
标解没看懂，直接说神仙做法。
考虑到一个很常规的trick是将入栈出栈操作转为括号序列。那么一个合法的数列的出栈方案一定对应着一个合法的括号序列。那其实题目就是在问合法的括号序列有多少种。
更严谨一点，我们想要证明充要性：
括号序列如果是合法的话，从后往前对每个右括号从大往小赋值，因为是合法的，一定有一个左括号与之匹配，左括号的值等于右括号的值，左括号所对应的就是原来的序列。所以一个合法的括号序列一定也对应着一个合法的出栈方案。
而限制条件其实就是 第 pospos 个左括号要匹配 第 valval 个右括号。
此时题目就变成一个很裸的卡特兰数了。枚举第 pospos 个左括号的位置为 ii ，可以计算出第 valval 个右括号的位置jj ,分别用卡特兰数计算 [1,i)[1,i) 和 [i+1,j)[i+1,j) 和 [j+1,n][j+1,n] 的方案，相乘，然后对每个位置的结果相加起来就是答案。
如果你是线性递推求逆元，时间是 O(n)O(n)
如果是费马小定理求逆元，时间是 O(nlog⁡mod)O(n \log mod)
法二有12倍的一个小常数，3.6e83.6e8(不是很能跑满) 略卡勉强通过。

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...