卡特兰数详解：从定义公式到经典应用与 C++ 实现

推导逻辑：总方案数 $\binom{2n}{n}$ 减去非法方案数 $\binom{2n}{n-1}$。

适用场景：n 较小（≤20）、无需取模（直接计算组合数）。 时间复杂度：$O(n)$（计算两个组合数）。

2.5 公式对比与选型建议

实际应用中，优先根据数据范围和取模要求选择公式：

• 小 n（≤20）：公式四（直接计算）；
• 中 n（≤1e5）：公式二（阶乘 + 逆元）；
• 大 n（≤1e6）：公式三（线性递推）；
• 模数非质数：公式一（递推规避除法）。

三、卡特兰数的经典应用

卡特兰数的应用场景看似零散，实则都符合'任意前缀操作数约束'的核心逻辑。以下是 6 类经典应用，帮你快速识别卡特兰数问题：

3.1 括号匹配问题

问题：n 对括号，有多少种合法匹配方式？ 示例：n=2 时，合法方式为 (())、()()，共 2 种（对应 $C_2=2$）。 核心逻辑：左括号数≥右括号数（任意前缀）。

3.2 栈的出栈序列问题

问题：1,2,…,n 依次入栈，有多少种合法出栈序列？ 示例：n=3 时，合法序列为 123、132、213、231、321，共 5 种（对应 $C_3=5$）。 核心逻辑：入栈次数≥出栈次数（任意前缀）。

3.3 购票找零问题

问题：n 人持 50 元、n 人持 100 元购票（票价 50 元），售票员无初始零钱，有多少种排队方式能顺利找零？ 示例：n=2 时，合法排队方式为 [50,50,100,100]、[50,100,50,100]，共 2 种（对应 $C_2=2$）。 核心逻辑：50 元人数≥100 元人数（任意前缀）。

3.4 二叉树构造问题

问题：n 个结点，能构造多少种不同的二叉搜索树（或普通二叉树）？ 示例：n=3 时，共 5 种（对应 $C_3=5$）。 核心逻辑：根节点左子树有 i 个结点，右子树有 n-1-i 个结点，所有拆分方式累加。

3.5 圆上点配对问题

问题：圆上有 2n 个点，两两相连且线段不交叉，有多少种配对方式？ 示例：n=3 时，共 5 种（对应 $C_3=5$）。 核心逻辑：固定一个点，与另一个点配对，将圆分成两部分，两部分的点各自配对不交叉。

3.6 阶梯搭建问题

问题：用 n 个 1×2 的矩形覆盖 2×n 的矩形，或用 n 个钢材搭建高度为 n 的阶梯（每步宽高均为 1），有多少种方式？ 示例：n=3 时，共 5 种（对应 $C_3=5$）。 核心逻辑：每一步选择'横向延伸'或'纵向延伸'，保证阶梯合法。

四、卡特兰数的 C++ 实现：5 道例题

4.1 例题 1：矩阵 II（洛谷 P1722）—— 模数非质数，用递推公式

题目链接：https://www.luogu.com.cn/problem/P1722

题目描述：给定 n，构造 1×2n 的矩阵，放入红色（+1）和黑色（-1）算筹，要求任意前缀红色数≥黑色数，且红黑数相等，求方案数对 100 取模的结果（n≤100）。 输入示例：2 → 输出示例：2

解题思路：

• 问题本质是 n 对括号的合法匹配，即卡特兰数 $C_n$；
• 模数 100 不是质数，无法用逆元处理除法，选择公式一（递推公式）；

递推公式：$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，避免溢出，同时满足题目要求。

4.2 例题 2：栈（洛谷 P1044）—— 无取模，用线性递推公式

题目链接：https://www.luogu.com.cn/problem/P1044

题目描述：给定 n，计算 1,2,…,n 依次入栈的合法出栈序列数（n≤18）。 输入示例：3 → 输出示例：5

解题思路：

• 问题本质是栈的合法出栈序列，即卡特兰数 $C_n$；
• 选择公式三（线性递推），效率最高，代码简洁。 n≤18，卡特兰数 $C_{18}=477638700$，未超过 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)$ 整除，无需担心除法精度问题。

4.3 例题 3：球迷购票问题（洛谷 P1754）—— 无取模，用线性递推公式

题目链接：https://www.luogu.com.cn/problem/P1754

题目描述：n 人持 50 元、n 人持 100 元购票（票价 50 元），售票员无初始零钱，求合法排队方式数（n≤20）。 输入示例：2 → 输出示例：2

解题思路：

• 问题本质是购票找零，即卡特兰数 $C_n$；
• n≤20，$C_{20}=6564120420$，仍在 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;
}

代码解析：与'栈的出栈序列'代码完全一致，体现了卡特兰数问题的共性；无需修改核心逻辑，仅需理解问题本质是卡特兰数应用。

4.4 例题 4：小猫配对（洛谷 P1375）—— 模数为质数，用通项公式

题目链接：https://www.luogu.com.cn/problem/P1375

题目描述：2n 只小猫站成一圈，两两配对且绳子不交叉，求方案数对 1e9+7 取模的结果（n≤1e5）。 输入示例：3 → 输出示例：5

解题思路：

• 问题本质是圆上点配对，即卡特兰数 $C_n$；
• n≤1e5，需高效计算，选择公式二（通项公式）；
• 模数 1e9+7 是质数，用费马小定理求逆元，处理除法 $\frac{1}{n+1}$。

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
LL comb(int n, int k) {
    if (n < 0 || k < 0 || n < k) return 0;
    return fact[n] * inv_fact[k] % MOD * inv_fact[n - k] % MOD;
}

// 计算卡特兰数 Cn mod MOD（公式二：通项公式）
LL catalan(int n) {
    return comb(2 * n, n) * qpow(n + 1, MOD - 2, MOD) % MOD;
}

int main() {
    int n;
    cin >> n;
    init(2 * n); // 预处理到 2n 的阶乘
    cout << catalan(n) << endl;
    return 0;
}

代码解析：

• 预处理阶乘和逆元：阶乘 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 的逆元（用快速幂计算）；
• 时间复杂度：预处理 $O(n)$，查询 $O(1)$，适合 n≤1e5 的场景。

4.5 例题 5：树屋阶梯（洛谷 P2532）—— 无取模，用高精度递推公式

题目链接：https://www.luogu.com.cn/problem/P2532

题目描述：用 n 个钢材搭建高度为 n 的阶梯（每步宽高均为 1），求搭建方式数（n≤500）。 输入示例：3 → 输出示例：5

解题思路：

• 问题本质是阶梯搭建，即卡特兰数 $C_n$；
• n≤500，$C_{500}$ 是极大数（远超 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] %= 10;
        }
    }
    for (int i = 0; i < M; ++i) res[i] = temp[i];
}

int main() {
    int n;
    cin >> n;
    // catalan[i] 存储 C_i，逆序存储（catalan[i][0] 是个位，catalan[i][1] 是十位...）
    int catalan[N][M] = {0};
    catalan[0][0] = 1; // C0=1

    // 公式一：递推计算 C1 到 Cn
    for (int i = 1; i <= n; ++i) {
        for (int j = 0; j < i; ++j) {
            int temp[M] = {0};
            // 计算 C_j * C_{i-1-j}
            for (int x = 0; x < M; ++x) {
                if (catalan[j][x] == 0) continue;
                for (int y = 0; y < M - x; ++y) {
                    temp[x + y] += catalan[j][x] * catalan[i - 1 - j][y];
                    temp[x + y + 1] += temp[x + y] / 10;
                    temp[x + y] %= 10;
                }
            }
            // 将 temp 加到 catalan[i] 中
            add(catalan[i], temp);
        }
    }

    // 输出结果：从高位到低位遍历，跳过前导零
    int p = M - 1;
    while (p >= 0 && catalan[n][p] == 0) --p;
    if (p < 0) cout << 0;
    else {
        while (p >= 0) cout << catalan[n][p--];
    }
    cout << endl;
    return 0;
}

代码解析：

• 高精度存储：用二维数组 catalan[N][M] 存储卡特兰数，catalan[i][j] 表示 $C_i$ 的第 j 位（逆序存储，方便进位处理）；
• 高精度乘法 + 加法：由于公式一是乘积之和，需先计算 $C_j \times C_{i-1-j}$（高精度乘法），再累加到 $C_i$ 中（高精度加法）；
• 输出处理：从高位到低位遍历，跳过前导零，得到正确结果；
• 时间复杂度：$O(n^2 \times M)$，n=500 时仍能高效运行。

五、卡特兰数的常见误区与避坑指南

5.1 溢出问题

• 小 n（≤20）：用 long long 存储；
• 中 n（≤1e5）：用取模 + 逆元（公式二）；
• 大 n（>1e5 或无取模）：用高精度计算（公式一）。

5.2 公式选型错误

• 模数非质数：避免用公式二、三（含除法），选择公式一；
• 大 n 快速计算：优先用公式三（线性递推）或公式二（预处理阶乘）；
• 小 n 直接计算：用公式四（组合数差）更直观。

5.3 问题本质识别错误

• 核心标志：两种操作、任意前缀一种操作数≥另一种；
• 反例：若无'任意前缀'约束，可能不是卡特兰数问题（如'n 对括号的所有排列数'是 $\binom{2n}{n}$，而非卡特兰数）。

5.4 高精度计算细节

• 存储顺序：逆序存储（低位在前），方便进位处理；
• 乘法进位：需双重循环遍历两个数的每一位，避免漏进位；
• 前导零：输出时跳过高位零，否则会输出多余的 0。

总结

通过本文的学习，你不仅能掌握卡特兰数的解法，更能理解组合数学中'抽象共性 + 具体实现'的思维方式。下次遇到括号匹配、栈操作、二叉树构造等问题时，不妨先判断是否为卡特兰数应用，再套用对应的公式和代码模板，轻松解决问题！