【7】卡特兰数学习笔记
前言感觉卡特兰数是非常实用的小技巧，一般在题目中以经典模型或发现递推式相同从而运用。就是典型的会的人秒掉，不会的人死都想不出来。
卡特兰数
定义
对于一个由 \(n\) 个 \(+1\) 和 \(n\) 个 \(-1\) 组成的序列，满足每个位置的前缀和 \(\ge 0\) 的不同的序列数称为 \(\text{Cat}_{n}\)，表示卡特兰数的第 \(n\) 项。
务必熟知这个概念，这个概念可以转化为以下三个经典问题。
\(1\)：由 \(n\) 对括号组成的不同的括号序列的数量为 \(\text{Cat}_{n}\)。
\(2\)：一个栈进栈序列 \(1,2,3\dots,n\) 的有 \(\text{Cat}_{n}\) 种不同的出栈序列。
\(3\)：大小为 \(n\times n\) 的方格图，起点为 \((0,0)\)，终点为 \((n,n)\)。每次只能向右或向上走一步，不能经过直线 \(y=x+1\) 上的点，合法路径数为 \(\text{Cat}_{n}\)。
递推式
边界情况为 \(\text{Cat}_{0}=1\)。
卡特兰数的递推式 \(1\) 为 \(\text{Cat}_{n}=\sum_{i=1}^n\text{Cat}_{i-1}\times \text{Cat}_{n-i}\)。
考虑问题 \(2\) 的另一种解法，设 \(f\) 表示前 \(n\) 个元素不同的出栈序列的数量。转移的话考虑枚举 \(n\) 是第 \(i\) 个出栈的元素，则前 \(i\) 个元素和后 \(i\) 个元素出栈顺序独立，由乘法原理得这种情况的方案数为 \(f\times f\)。最后由加法原理把不同的 \(i\) 的方案数加起来。
因此，有 \(\text{Cat}_{n}=\sum_{i=1}^n\text{Cat}_{i-1}\times \text{Cat}_{n-i}\)。
卡特兰数的递推式 \(2\) 为 \(\text{Cat}_{n}=\text{Cat}_{n-1}\times\frac{4n-2}{n+1}\)。
我们利用卡特兰数的通项公式(见下一板块)，直接带入通项公式就可以证明。
\[\begin{aligned}\text{Cat}_n &= C_{2n}^n-C_{2n}^{n+1} \\ &= \frac{(2n)!}{(2n-n)!(n)!}-\frac{(2n)!}{(2n-n-1)!(n+1)!}\\ &= \frac{(2n)!}{(n)!^2}-\frac{(2n)!}{(n)!^2\frac{n+1}{n}}\\ &= \frac{(2n)!}{n!^2(n+1)}\\\end{aligned}\]
将 \(n\) 用 \(n-1\) 代换后相除得到递推系数。
\[\text{Cat}_{n-1}=\frac{(2n-2)!}{(n-1)!^2n}\]
\[\begin{aligned}\frac{\text{Cat}_n}{\text{Cat}_{n-1}}&=\frac{\frac{(2n)!}{(n)!^2(n+1)}}{\frac{(2n-2)!}{(n-1)!^2n}}\\ &=\frac{(n-1)!^2n(2n)!}{n!^2(n+1)(2n-2)!}\\ &=\frac{n\times 2n(2n-1)}{n^2(n+1)}\\ &=\frac{4n-2}{n+1}\end{aligned}\]
因此，有 \(\text{Cat}_{n}=\text{Cat}_{n-1}\times\frac{4n-2}{n+1}\)。
由递推式相同，我们还可以推出卡特兰数可以转化为这三个经典问题。
\(4\)：由 \(n\) 个节点可以构成 \(\text{Cat}_{n}\) 棵不同的二叉树。
\(5\)：在圆中选择 \(n\) 个点对，使这些点对连成的 \(n\) 条线段互不相交的方案数为 \(\text{Cat}_{n}\)。
\(6\)：对角线不相交的情况下，将一个凸多边形区域分成三角形区域的方法数为 \(\text{Cat}_{n}\)。
通项公式
卡特兰数的通项公式为 \(\text{Cat}_{n}=C_{2n}^n-C_{2n}^{n+1}\)，其中 \(C\) 为组合数。
考虑问题 \(3\) 的另一种解法，显然，考虑分配向上和向右的一步的位置，从 \((x,y)\) 走到 \((n,n)\) 只能向右或向上的路径数为 \(C_{n-x}^{n-y}\)。
使用反射容斥，不合法的路径的方案数等价于从 \((-1,1)\) 到 \((n,n)\) 的方案数。因为如果碰到直线 \(y=x+1\) 上的点，就把从起点到这个碰到的点的路径沿 \(y=x+1\) 翻折。显然不合法路径和从 \((-1,1)\) 到 \((n,n)\) 的路径一一对应，形成双射。不合法路径的数量即为 \(C_{2n}^{n+1}\)。
因此，有 \(\text{Cat}_{n}=C_{2n}^n-C_{2n}^{n+1}\)。
例题
例题 \(1\) ：
P2532 树屋阶梯
首先每一列最上面的那些木块任意两个不能被包含在同一个长方形中，而这样的木块有 \(n\) 个，长方形也只有 \(n\) 个，因此每个长方形右上角必然为某一列最上面的木块。
直接求做不了，考虑递推。设 \(f\) 为 \(n\) 级阶梯的方案数，枚举最后一个长方形的右上角，把图分成了左上角的阶梯和右下角的阶梯。这两个阶梯是完全相同且独立的子问题，可以直接乘法原理合并得出转移式。
\=\sum_{i=1}^n ff\]
发现这就是卡特兰数的递推式 \(1\)，使用卡特兰数的递推式 \(2\) 加上高精度就做完了。
#include <bits/stdc++.h>
using namespace std;
int n,ans;
void mul(int x)
{
int flag=0;
for(int i=1;i<=50000;i++)ans=ans*x+flag,flag=ans/10,ans%=10;
}
void div(int x)
{
int flag=0;
for(int i=50000;i>=1;i--)ans+=flag*10,flag=ans%x,ans=ans/x;
}
int main()
{
scanf("%d",&n);
ans=1;
for(int i=2;i<=n;i++)mul(4*i-2),div(i+1);
bool flag=0;
for(int i=50000;i>=1;i--)
if(flag||ans)printf("%d",ans),flag=1;
return 0;
}小技巧：熟记卡特兰数前几项 \(1,1,2,5,14,42,132\dots\)，看到第 \(3\) 项为 \(5\) 直接猜卡特兰数，写一发过了，证明确实是卡特兰数。
例题 \(2\) ：
P3200 有趣的数列
由于奇数项和偶数项又分开的限制，所以我们从小到大考虑每个数是填在奇数项的第一个可用的位置还是偶数项的第一个可用的位置。
如果已经填入的偶数项的数大于奇数项的数，假设奇数项填到了 \(2k-1\)，因为至少多一项，那偶数项至少填到了 \(2k+2\)。由于从小到大填，则下一个奇数项 \(2k+1\) 必然大于 \(2k+2\) 的数，与条件 \(3\) 奇数项小于偶数项矛盾。
因此，我们可以把填在奇数项看作左括号，填在偶数项看作右括号，就转化为了合法括号序列计数问题，答案就是卡特兰数。
由于模数不一定是质数，逆元不一定存在，所以我们选用递推式 \(2\) 加分解质因数求最终答案。
#include using namespace std;int n,mod,ans=1,pr,dm,cnt=0;bool b;mapp;int power(int a,int p){ int x=a,ans=1; while(p) { if(p&1)ans=1ll*ans*x%mod; p>>=1; x=1ll*x*x%mod; } return ans;}void init(int mx){ b=1; for(int i=2;i>1]%mod; ans=now; } for(int i=1;i
页:
[1]