C++算法
卡特兰数详解：从定义公式到经典应用与 C++ 实现
卡特兰数是组合数学中的经典数列，广泛应用于括号匹配、栈操作、二叉树计数等问题。文章详细讲解其定义、四种核心计算公式及适用场景，通过五道 C++ 例题演示不同数据范围下的解法选择与实现细节，涵盖取模、无取模及高精度计算，帮助掌握识别与应用卡特兰数问题的技巧。
卡特兰数是组合数学中的经典数列，广泛应用于括号匹配、栈操作、二叉树计数等问题。文章详细讲解其定义、四种核心计算公式及适用场景，通过五道 C++ 例题演示不同数据范围下的解法选择与实现细节，涵盖取模、无取模及高精度计算，帮助掌握识别与应用卡特兰数问题的技巧。
卡特兰数是一组满足特定递推关系的整数序列，记为 $C_n$（$n\ge0$），其中第 n 项表示 n 个'操作对'对应的合法方案数。
前 11 项卡特兰数（n 从 0 到 10）如下：
| n（项数） | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|---|
| $C_n$（卡特兰数） | 1 | 1 | 2 | 5 | 14 | 42 | 132 | 429 | 1430 | 4862 | 16796 |
从数列可以看出，卡特兰数增长速度极快，n=10 时已达 16796，n=20 时更是突破 6564120420，因此大规模计算时需注意溢出问题（通常用取模或高精度处理）。
卡特兰数的核心本质是：在两种对立操作的序列中，保证任意前缀中一种操作数不小于另一种操作数。
比如：
这些问题的共性，正是卡特兰数的应用场景标志。
卡特兰数有 4 种常用公式，分别适用于不同场景（如数据范围、是否取模、是否需要递推打表），掌握它们就能应对所有卡特兰数问题。
$$C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$$
推导逻辑：将规模为 n 的问题拆分为两个子问题。以'n 个结点构造二叉树'为例：选择第 i 个结点作为根节点；总方案数为所有拆分方式的累加。 右子树有 n-1-i 个结点，方案数为 $C_{n-1-i}$；左子树有 i 个结点，方案数为 $C_i$。
适用场景：n 较小（≤100）、需要规避除法（如取模的模数不是质数）。 时间复杂度：$O(n^2)$。
$$C_n = \frac{1}{n+1}\binom{2n}{n}$$
推导逻辑：从 2n 个位置中选择 n 个位置放置'左操作'，总方案数为 $\binom{2n}{n}$；再减去非法方案数，最终得到上述通项公式。
适用场景：n 中等（≤1e5）、模数为质数（可通过逆元处理除法）。 时间复杂度：$O(n)$（预处理阶乘和逆元后，单次查询 $O(1)$）。
$$C_n = C_{n-1} \times \frac{4n-2}{n+1}$$
推导逻辑：由通项公式变形得到，避免了组合数计算，直接通过前一项递推当前项。
适用场景：n 中等（≤1e6）、无需取模（或模数支持除法）、需要快速打表。 时间复杂度：$O(n)$（线性递推，效率极高）。
$$C_n = \binom{2n}{n} - \binom{2n}{n-1}$$
推导逻辑：总方案数 $\binom{2n}{n}$ 减去非法方案数 $\binom{2n}{n-1}$。
适用场景：n 较小（≤20）、无需取模（直接计算组合数）。 时间复杂度：$O(n)$（计算两个组合数）。
| 公式类型 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|
| 递推公式（公式一） | 无除法、逻辑直观 | 时间复杂度 $O(n^2)$ | n≤100、模数非质数 |
| 通项公式（公式二） | 组合数本质、支持大 n | 需要处理除法（逆元） | n≤1e5、模数为质数 |
| 线性递推（公式三） | 效率最高（$O(n)$）、代码简洁 | 除法可能溢出 | n≤1e6、无需取模或模数支持除法 |
| 组合数差（公式四） | 逻辑简单（正难则反） | 组合数计算可能溢出 | n≤20、直接计算（无取模） |
实际应用中，优先根据数据范围和取模要求选择公式：
卡特兰数的应用场景看似零散，实则都符合'任意前缀操作数约束'的核心逻辑。以下是 6 类经典应用，帮你快速识别卡特兰数问题：
问题：n 对括号，有多少种合法匹配方式？
示例：n=2 时，合法方式为 (())、()()，共 2 种（对应 $C_2=2$）。
核心逻辑：左括号数≥右括号数（任意前缀）。
问题：1,2,…,n 依次入栈，有多少种合法出栈序列？ 示例：n=3 时，合法序列为 123、132、213、231、321，共 5 种（对应 $C_3=5$）。 核心逻辑：入栈次数≥出栈次数（任意前缀）。
问题：n 人持 50 元、n 人持 100 元购票（票价 50 元），售票员无初始零钱，有多少种排队方式能顺利找零？ 示例：n=2 时，合法排队方式为 [50,50,100,100]、[50,100,50,100]，共 2 种（对应 $C_2=2$）。 核心逻辑：50 元人数≥100 元人数（任意前缀）。
问题：n 个结点，能构造多少种不同的二叉搜索树（或普通二叉树）？ 示例：n=3 时，共 5 种（对应 $C_3=5$）。 核心逻辑：根节点左子树有 i 个结点，右子树有 n-1-i 个结点，所有拆分方式累加。
问题：圆上有 2n 个点，两两相连且线段不交叉，有多少种配对方式？ 示例：n=3 时，共 5 种（对应 $C_3=5$）。 核心逻辑：固定一个点，与另一个点配对，将圆分成两部分，两部分的点各自配对不交叉。
问题：用 n 个 1×2 的矩形覆盖 2×n 的矩形，或用 n 个钢材搭建高度为 n 的阶梯（每步宽高均为 1），有多少种方式？ 示例：n=3 时，共 5 种（对应 $C_3=5$）。 核心逻辑：每一步选择'横向延伸'或'纵向延伸'，保证阶梯合法。
题目链接：https://www.luogu.com.cn/problem/P1722
题目描述：给定 n，构造 1×2n 的矩阵，放入红色（+1）和黑色（-1）算筹，要求任意前缀红色数≥黑色数，且红黑数相等，求方案数对 100 取模的结果（n≤100）。 输入示例：2 → 输出示例：2
解题思路：
递推公式：$C_n = \sum_{i=0}^{n-1} C_i C_{n-1-i}$，对 100 取模。
C++ 代码实现
#include <iostream>
using namespace std;
const int N = 110;
const int MOD = 100; // 非质数，规避除法
int main() {
int n;
cin >> n;
int catalan[N] = {0};
catalan[0] = 1; // 初始项 C0=1
// 公式一：递推计算 C1 到 Cn
for (int i = 1; i <= n; ++i) {
for (int j = 0; j < i; ++j) {
catalan[i] = (catalan[i] + catalan[j] * catalan[i - j - 1]) % MOD;
}
}
cout << catalan[n] << endl;
return 0;
}
代码解析：用数组 catalan 存储卡特兰数，初始项 catalan[0]=1；双重循环实现递推，外层循环计算第 i 项，内层循环累加所有子问题的乘积；每步取模 100，避免溢出，同时满足题目要求。
题目链接：https://www.luogu.com.cn/problem/P1044
题目描述：给定 n，计算 1,2,…,n 依次入栈的合法出栈序列数（n≤18）。 输入示例：3 → 输出示例：5
解题思路：
long long 范围（最大值 9e18）；C++ 代码实现
#include <iostream>
using namespace std;
typedef long long LL;
int main() {
int n;
cin >> n;
LL catalan = 1; // C0=1
// 公式三：线性递推 Cn = Cn-1 * (4n-2)/(n+1)
for (int i = 1; i <= n; ++i) {
catalan = catalan * (4 * i - 2) / (i + 1);
}
cout << catalan << endl;
return 0;
}
代码解析：用 long long 存储结果，避免 n=18 时溢出；线性递推公式无需双重循环，时间复杂度 $O(n)$；由于卡特兰数是整数，$(4i-2)$ 必能被 $(i+1)$ 整除，无需担心除法精度问题。
题目链接：https://www.luogu.com.cn/problem/P1754
题目描述：n 人持 50 元、n 人持 100 元购票（票价 50 元），售票员无初始零钱，求合法排队方式数（n≤20）。 输入示例：2 → 输出示例：2
解题思路：
long long 范围；C++ 代码实现
#include <iostream>
using namespace std;
typedef long long LL;
int main() {
int n;
cin >> n;
LL catalan = 1;
for (int i = 1; i <= n; ++i) {
catalan = catalan * (4 * i - 2) / (i + 1);
}
cout << catalan << endl;
return 0;
}
代码解析：与'栈的出栈序列'代码完全一致，体现了卡特兰数问题的共性；无需修改核心逻辑，仅需理解问题本质是卡特兰数应用。
题目链接：https://www.luogu.com.cn/problem/P1375
题目描述：2n 只小猫站成一圈，两两配对且绳子不交叉，求方案数对 1e9+7 取模的结果（n≤1e5）。 输入示例：3 → 输出示例：5
解题思路：
C++ 代码实现
#include <iostream>
using namespace std;
typedef long long LL;
const int MOD = 1e9 + 7;
const int N = 2e5 + 10; // 2n 最大为 2e5
LL fact[N]; // fact[i] = i! mod MOD
LL inv_fact[N]; // inv_fact[i] = (i!)^-1 mod MOD
// 快速幂：计算 a^b mod p（费马小定理求逆元）
LL qpow(LL a, LL b, LL p) {
LL res = 1;
while (b) {
if (b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
// 预处理阶乘和阶乘逆元
void init(int max_n) {
fact[0] = 1;
for (int i = 1; i <= max_n; ++i) {
fact[i] = fact[i - 1] * i % MOD;
}
// 费马小定理：inv_fact[max_n] = (max_n!)^(MOD-2) mod MOD
inv_fact[max_n] = qpow(fact[max_n], MOD - 2, MOD);
for (int i = max_n - 1; i >= 0; --i) {
inv_fact[i] = inv_fact[i + 1] * (i + 1) % MOD;
}
}
// 计算组合数 C(n, k) mod MOD
{
(n < || k < || n < k) ;
fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}
{
( * n, n) * (n + , MOD - , MOD) % MOD;
}
{
n;
cin >> n;
( * n);
cout << (n) << endl;
;
}
代码解析：
fact[i] 存储 $i! \pmod{MOD}$，逆元 inv_fact[i] 存储 $(i!)^{-1} \pmod{MOD}$；comb(n, k) = n!/(k!*(n-k)!) mod MOD，通过阶乘和逆元实现；catalan(n) = C(2n, n) * inv(n+1) mod MOD，其中 inv(n+1) 是 n+1 的逆元（用快速幂计算）；题目链接：https://www.luogu.com.cn/problem/P2532
题目描述：用 n 个钢材搭建高度为 n 的阶梯（每步宽高均为 1），求搭建方式数（n≤500）。 输入示例：3 → 输出示例：5
解题思路：
long long 范围），需用高精度计算；C++ 代码实现
#include <iostream>
using namespace std;
const int N = 510; // 最大 n=500
const int M = 1000; // 高精度数组长度（足够存储 C500）
// 高精度加法：a = a + b（a、b 为逆序存储的大整数，低位在前）
void add(int a[], int b[]) {
for (int i = 0; i < M - 1; ++i) {
a[i] += b[i];
a[i + 1] += a[i] / 10; // 进位
a[i] %= 10; // 取当前位
}
}
// 高精度乘法：res = a * b（res 为逆序存储的大整数）
void multiply(int res[], int a[], int b[]) {
static int temp[M] = {0};
for (int i = 0; i < M; ++i) temp[i] = 0;
for (int x = 0; x < M; ++x) {
if (a[x] == 0) continue;
for (int y = 0; y < M - x; ++y) {
temp[x + y] += a[x] * b[y];
temp[x + y + 1] += temp[x + y] / 10;
temp[x + y] %= ;
}
}
( i = ; i < M; ++i) res[i] = temp[i];
}
{
n;
cin >> n;
catalan[N][M] = {};
catalan[][] = ;
( i = ; i <= n; ++i) {
( j = ; j < i; ++j) {
temp[M] = {};
( x = ; x < M; ++x) {
(catalan[j][x] == ) ;
( y = ; y < M - x; ++y) {
temp[x + y] += catalan[j][x] * catalan[i - - j][y];
temp[x + y + ] += temp[x + y] / ;
temp[x + y] %= ;
}
}
(catalan[i], temp);
}
}
p = M - ;
(p >= && catalan[n][p] == ) --p;
(p < ) cout << ;
{
(p >= ) cout << catalan[n][p--];
}
cout << endl;
;
}
代码解析：
catalan[N][M] 存储卡特兰数，catalan[i][j] 表示 $C_i$ 的第 j 位（逆序存储，方便进位处理）；long long 存储；通过本文的学习，你不仅能掌握卡特兰数的解法，更能理解组合数学中'抽象共性 + 具体实现'的思维方式。下次遇到括号匹配、栈操作、二叉树构造等问题时，不妨先判断是否为卡特兰数应用，再套用对应的公式和代码模板，轻松解决问题！
微信公众号「极客日志」，在微信中扫描左侧二维码关注。展示文案：极客日志 zeeklog
使用加密算法（如AES、TripleDES、Rabbit或RC4）加密和解密文本明文。 在线工具，加密/解密文本在线工具，online
将字符串编码和解码为其 Base64 格式表示形式即可。 在线工具，Base64 字符串编码/解码在线工具，online
将字符串、文件或图像转换为其 Base64 表示形式。 在线工具，Base64 文件转换器在线工具，online
将 Markdown（GFM）转为 HTML 片段，浏览器内 marked 解析；与 HTML转Markdown 互为补充。 在线工具，Markdown转HTML在线工具，online
将 HTML 片段转为 GitHub Flavored Markdown，支持标题、列表、链接、代码块与表格等；浏览器内处理，可链接预填。 在线工具，HTML转Markdown在线工具，online
通过删除不必要的空白来缩小和压缩JSON。 在线工具，JSON 压缩在线工具，online