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

· · 个人记录

是一个组合数学的数列，通项公式如下

C_n=\frac{1}{n+1}\begin{pmatrix}2n\\n\end{pmatrix}

递推公式如下

C_n=\sum_{i=0}^{n-1}C_i\times C_{n-i-1}

特别的 C_0=1

卡特兰数一般用来解决以下问题:

你要问这个数有什么具体意义吗，我感觉没啥意义吧，就比如斐波那契数列也没有什么很特别的意义。它只是适合解决上面这一类问题。

现在来两个经典例子。

括号序列

问题:求长度为 n 对(不是 n 个)括号的合法序列数。

求解思路:

  1. 任何一个非空的合法括号序列，第一个字符一定是左括号(
  2. 这个左括号一定对应一个右括号 )，它们之间是一个合法的括号序列，右边也是一个合法的括号序列

即形如(A)B

那么A的方案数为 C_{i-1} B的方案数为 C_{n-i-1}

总方案数显然是卡特兰数

路径计数

问题:在网格图中从 (0,0) 到 (n,n) 不越过对角线的路径数。

做法很多，这里介绍反射变换。

不考虑限制，总路线显然是 \begin{pmatrix}2n\\n\end{pmatrix}

考虑除去非法部分，将这条路径在第一次碰到 y=x+1 之后的部分，关于直线 y=x+1 作对称。

终点变为 (n-1,n+1)

容易想到 (0,0) 到 (n-1,n+1) 的总路径数反射回去一定是非法的(也容易想到所有非法的一定能反射，不懂的可以手画个图)

这种方案数是 \begin{pmatrix}2n\\n-1\end{pmatrix}

两者相减，得

\begin{pmatrix}2n\\n\end{pmatrix}-\begin{pmatrix}2n\\n-1\end{pmatrix} =\frac{(2n)!}{n!\times n!}- (\frac{n}{n+1}\times \frac{(2n)!}{{n!} \times n!}) =\frac{1}{n+1}\begin{pmatrix}2n\\n\end{pmatrix}

显然是卡特兰数通项公式。

例题

A.消失的序列

机房学生吊打标解时刻%%%

当出题人还在用卡特兰数卷积，正解还在写极为复杂的分类讨论dp，某位大神则将其变为括号序列问题吊打标程，成为了今日的神话。

题意: 某个神人对一个数列有一种排序方式，它的排序方式有以下两种:

  1. 从弹出数列第一个数压入栈中
  2. 从栈顶弹出一个数(到已弹出数列的最后)

这个神人原本有一个数列，而且它记得它的数列可以通过这种方式将数列排序成有序的(小到大)。但是它却不记得原本数列是什么了，只记得一个位置 pos 填的是 val ，问你它原本的数列有多少种可能。

(这神人记性真好)

这个数列是一个 [1,n] 的排列，每次给定n,pos,val

n \le 10^6

::::info[神仙做法] 标解没看懂，直接说神仙做法。

考虑到一个很常规的trick是将入栈出栈操作转为括号序列。那么一个合法的数列的出栈方案一定对应着一个合法的括号序列。那其实题目就是在问合法的括号序列有多少种。

更严谨一点，我们想要证明充要性：

括号序列如果是合法的话，从后往前对每个右括号从大往小赋值，因为是合法的，一定有一个左括号与之匹配，左括号的值等于右括号的值，左括号所对应的就是原来的序列。所以一个合法的括号序列一定也对应着一个合法的出栈方案。

而限制条件其实就是 第 pos 个左括号要匹配 第 val 个右括号。

此时题目就变成一个很裸的卡特兰数了。枚举第 pos 个左括号的位置为 i ，可以计算出第 val 个右括号的位置j ,分别用卡特兰数计算 [1,i) 和 [i+1,j) 和 [j+1,n] 的方案，相乘，然后对每个位置的结果相加起来就是答案。

如果你是线性递推求逆元，时间是 O(n)

如果是费马小定理求逆元，时间是 O(n \log mod)

法二有12倍的一个小常数，3.6e8(不是很能跑满) 略卡勉强通过。 ::::