Catalan 数CSP-S

💡 核心思想

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

🎯 直觉理解

想象你在走一个网格，从左上角到右下角，只能向右或向下走，而且不能走到对角线下方。问有多少种走法？这就是 Catalan 数的经典场景。另一个经典场景是：n 对括号的合法排列数。比如 n=3 时，有 5 种：((())), (()()), (())(), ()(()), ()()()。

📝 算法流程

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;
}

⚠️ 常见坑点

📚 相关题目