什么是卡特兰数
以下看似毫不相关的问题均属于 Catalan 数列：
- \(n\) 个节点能够构成 \(Cat_n\) 种不同的二叉树
- \(n\) 个左括号与 \(n\) 个右括号组成的合法序列有 \(Cat_n\) 种
- \(n\) 个元素按照大小进栈，合法的出栈序列有 \(Cat_n\) 种
- 通过诺干条互不相交的对角线，把凸多边形拆分成若干个三角形的方案数为 \(Cat_n\)
- 在平面直角坐标系上，每一步只能向上或向右行走一个单位长度，从 \((0,0)\) 走到 \(n,n\) 并且不接触直线 \(y=x\) 的路径数量为 \(2Cat_n\)
卡特兰序列的前几项为：
| \(Cat_0\) | \(Cat_1\) | \(Cat_2\) | \(Cat_3\) | \(Cat_4\) | \(Cat_5\) | ... |
|---|---|---|---|---|---|---|
| \(1\) | \(1\) | \(2\) | \(5\) | \(14\) | \(42\) | ... |
关于卡特兰数的常见公式：
\[\begin{aligned} \\ Cat_n &= \frac{\begin{pmatrix} 2n \\ n \end{pmatrix}}{n+1} \ \ \ \ \ \ (n>2) \\ \\ Cat_n &= \begin{pmatrix} 2n \\ n \end{pmatrix} - \begin{pmatrix} 2n \\ n-1 \end{pmatrix} \\ \\ Cat_n &= \frac{Cat_{n-1}(4n-2)}{n+1} \\ \\ Cat_n &= \begin{cases}{\sum_{i=1}^{n}Cat_{i-1} \times Cat_{n-i} \ \ \ \ (n>2)} \\ {1 \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ (n=0,1)}\end{cases} \\ \end{aligned} \]一些例题
用卡特兰数公式求出 \(Cat_n\) 即可
#include <cstdio>
typedef long long ll;
using namespace std;
ll ans=1; // 答案较大,要开long long
int n;
signed main() {
scanf("%d",&n);
for(int i=2;i<=n;++i)
ans=ans*((i<<2)-2)/(i+1); // 递推式
// 由于我们只需要求 Cat[n]
// Cat[i] 只和 Cat[i-1] 有关
// 所以我们可以用滚动数组优化成一个变量
printf("%lld",ans);
return 0;
}
本题是求凸多边形三角划分，直接求 \(Cat_n\) ，用组合数求出即可
#include <cstdio>
typedef long long ll;
using namespace std;
const ll Mod=1e9+7;
const int N=3e5+7;
ll fac[N];
int n;
inline ll mi(ll mi_a,ll mi_b,ll mi_mod) {
ll mi_ans=1;
for(;mi_b;mi_a=mi_a*mi_a%mi_mod,mi_b>>=1)
(mi_b&1)&&(mi_ans=mi_ans*mi_a%mi_mod);
return mi_ans;
}
inline ll C(ll n,ll m,ll p) {
return fac[n]*mi(fac[m],p-2,p)%p*mi(fac[n-m],p-2,p)%p; // 用费马小定理求逆元
}
signed main() {
scanf("%d",&n);
fac[0]=1;
for(int i=1;i<N;++i)
fac[i]=(fac[i-1]*i)%Mod; // 预处理, fac[i]=i!
printf("%lld",((C(2*n,n,Mod)-C(2*n,n-1,Mod))%Mod+Mod)%Mod); // 直接套 Catalan 组合数公式
return 0;
}
打表可以发现这题就是让我们求 \(Cat_n\)
但实际上，我们可以从DP 的角度考虑这道题。对于任意大小为 \(n\) 的阶梯，我们都可以现在左下角放一个大块，然后在上方构造一个大小为 \(i\) 的阶梯，右下方构造大小为 \(n-i-1\) 的阶梯，那么转移方程就是
\[f_i = \sum^{n-1}_{i=0}f_i \times f_{n-i-1} \]容易看出这就是 Catalan 数
注意高精
还有一些有思维难度的例题，请读者们自己思考一下