数论之卡特兰数

2020-12-01

1、基本模型

有一个长度为 \(2n\)\(01\)序列,其中\(1,0\)\(n\)个,要求对于任意的整数 $k \in [1,2n] $,数列的前 \(k\)个数中,\(1\)的个数不少于\(0\)

满足条件的序列的数量为

\[Cat_n=\frac{C_{2n}^n}{n+1} \]

另一种形式

\[Cat_n=C_{2n}^n-C_{cn}^{n-1} \]

又一种形式

\[Cat(n)=\frac{1}{n+1}\sum_{i=0}^n{C_n^i}^2 \]

递推式

\[Cat_n=\sum_{i=0}^{n-1}Cat_i \times Cat_{n-i-1} \]

\[Cat(n+1)=\frac{2(2n+1)}{n+2}Cat(n) \]

2、证明

主要是运用了翻折的思想

传送门

可以通过这种方法得出更为普遍的结论

比如这道题

3、推论

以下问题都与卡特兰数有关

\(1\)\(n\)个左括号和\(n\)个右括号组成的合法括号序列的数量为\(Cat_n\)

\(2\)\(1,2,...,n\)经过一个栈,形成的合法出栈序列的数量为\(Cat_n\)

\(3\)\(n\)个节点构成的不同二叉树的数量为\(Cat_n\)

\(4\)、在平面直角坐标系上,每一步只能向上或向右走,从\((0,0)\)走到\((n,n)\)并且除两个端点外不接触直线\(y=x\)的路线数量为\(2Cat_n-1\)

\(5\)、对凸 \(n+2\) 边形进行不同的三角形分割的方案数(分割线断点仅为顶点,且分割线仅在顶点上相交)

\(6\)\(n\) 层的阶梯切割为 \(n\) 个矩形的切法数

4、解题思路

\(1\)、通过递推式得到卡特兰数

比如这道题

\(2\)、可以将题目转化为卡特兰数的模型

比如这道题

\(3\)、还可以找规律

卡特兰数的前几项:\(1,1,2,5,14,42,132\)

5、一些技巧

卡特兰的题目有很多需要高精度,建议学习一下我的高精度板子

还有一些题目给出的模数不是质数

我们可以把模数分解质因数,求出在模每一个质数下的答案,再用中国剩余定理和到一起

但是还有一种更简单的方法

因为分子比分母中一定存在数量更多的(或一样多)的因数 \(p\)

于是可以分别算出分子和分母中含有的某个质数 \(p\) 的指数是多少

再用上面的指数减去下面的指数,做一个快速幂就行了

\(n!\)\(p\) 的指数

int cnt=0;
while(n){
	n/=p;
	cnt+=;
}