Catalan 数NOIP

💡 核心思想

Catalan 数是一组重要的组合数，出现在多种计数问题中：合法的括号序列数、二叉树形态数、网格路径不跨越对角线的方案数、出栈顺序数等。第 n 个 Catalan 数为 C(2n,n)/(n+1) = C(2n,n) - C(2n,n+1)。递推式：C₀=1, Cₙ₊₁ = Σ Cᵢ·Cₙ₋ᵢ。

🎯 直觉理解

Catalan 数是一系列"看似不同、本质相同"的组合计数的答案：n 对括号的合法括号序列数、n 个节点的二叉搜索树数、$n imes n$ 网格不越过对角线的路径数……它们都等于 $C_n=\frac{1}{n+1}C(2n,n)$。

递推：$C_0=1$，$C_n=sum_{i=0}^{n-1}C_i imes C_{n-1-i}$——"把第一个元素的划分枚举出来"：左边 i 个、右边 n-1-i 个，两部分独立计数相乘再求和。

做题套路：先背前几项（1, 1, 2, 5, 14, 42, 132），看到"括号匹配、进出栈、二叉树计数、不越线路径"这些关键词，验证几项符合就套 Catalan。

📝 算法流程

1. 公式法：Cat(n) = C(2n, n) / (n + 1)
2. 递推法：Cat(0) = 1, Cat(n+1) = Σ Cat(i)·Cat(n-i)
3. 线性递推：Cat(n) = Cat(n-1) · (4n-2) / (n+1)
4. 预处理阶乘+逆元可在 O(1) 查询

$$Cat_n = \frac{1}{n+1} \binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}$$

$$Cat_{n+1} = \sum_{i=0}^{n} Cat_i \cdot Cat_{n-i}$$

📊 复杂度分析

💻 参考实现（C++）

#include 
using namespace std;
using ll = long long;
const int MOD = 1e9 + 7;

ll fac[200005], inv[200005];

ll qpow(ll a, ll n) {
    ll res = 1; a %= MOD;
    while (n) { if (n & 1) res = res * a % MOD; a = a * a % MOD; n >>= 1; }
    return res;
}

void init(int n) {
    fac[0] = 1;
    for (int i = 1; i <= n; i++) fac[i] = fac[i-1] * i % MOD;
    inv[n] = qpow(fac[n], MOD - 2);
    for (int i = n-1; i >= 0; i--) inv[i] = inv[i+1] * (i+1) % MOD;
}

ll C(ll n, ll m) {
    if (m > n || m < 0) return 0;
    return fac[n] * inv[m] % MOD * inv[n-m] % MOD;
}

ll catalan(int n) {
    return C(2*n, n) * qpow(n + 1, MOD - 2) % MOD;
}

int main() {
    init(100000);
    for (int i = 0; i <= 10; i++)
        cout << "Cat(" << i << ")=" << catalan(i) << " ";
    // Cat(0)=1 Cat(1)=1 Cat(2)=2 Cat(3)=5 Cat(4)=14 ...
    cout << endl;
    return 0;
}

⚠️ 常见坑点

📚 相关题目