深入探讨卡特兰数与斯特林数的动态规划实现

核心逻辑与数学原理

1. 卡特兰数（Catalan Number）

卡特兰数是组合数学中最常见的特殊计数序列之一。记第 $n$ 项为 $H_n$，其标准通项公式为：

$$H_n = \frac{C_{2n}^n}{n + 1} = C_{2n}^n - C_{2n}^{n-1}$$

其通项满足以下高效的代数递推式：

$$H_n = \frac{4n - 2}{n + 1} H_{n-1} \, (H_0 = 1)$$

格路模型证明

在平面直角坐标系中，从 $(0,0)$ 出发，每次只能向右或向上移动 $1$ 个单位，求走到 $(n,n)$且途径任意点 $(x,y)$ 时均满足 $x \geq y$（即不穿过直线 $y=x$）的非降路径数。

无限制总路径数：相当于从 $2n$ 步中选出 $n$ 步向右，总数为 $C_{2n}^n$。
不合法路径数：任何穿过 $y=x$ 的路径，必然会触及或越过直线 $y=x+1$。设不合法路径第一次触及 $y=x+1$ 的点为 $P$。将 $P$ 点之后的路径关于直线 $y=x+1$ 进行对称翻转。
翻转后，路径的终点 $(n,n)$ 将对称映射到 $(n-1, n+1)$。由于每一条触及 $y=x+1$ 走到 $(n,n)$ 的不合法路径与走到 $(n-1, n+1)$ 的路径形成一一对应，故不合法路径总数为 $C_{2n}^{n-1}$。用总数减去不合法数，即得标准通项 $C_{2n}^n - C_{2n}^{n-1}$。

2. 第一类斯特林数（Stirling Number of the First Kind）

具有符号的第一类斯特林数 $\begin{bmatrix} n \\ k \end{bmatrix}$（记作 $s(n,k)$），表示将 $n$ 个不同的元素构成 $k$ 个互不相交的圆排列（环）的方案数。其状态组合递推逻辑为：

$$\begin{bmatrix} n \\ k \end{bmatrix} = \begin{bmatrix} n-1 \\ k-1 \end{bmatrix} + (n-1) \times \begin{bmatrix} n-1 \\ k \end{bmatrix}$$

边界：$\begin{bmatrix} 0 \\ 0 \end{bmatrix} = 1$，若 $n > 0$ 则 $\begin{bmatrix} n \\ 0 \end{bmatrix} = 0$。

3. 第二类斯特林数（Stirling Number of the Second Kind）

第二类斯特林数 $\begin{Bmatrix} n \\ k \end{Bmatrix}$（记作 $S(n,k)$），表示将 $n$ 个不同的元素拆分成 $k$ 个非空且无区别的子集（集合）的方案数。其状态合并递推逻辑为：

$$\begin{Bmatrix} n \\ k \end{Bmatrix} = \begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix} + k \times \begin{Bmatrix} n-1 \\ k \end{Bmatrix}$$

边界：$\begin{Bmatrix} 0 \\ 0 \end{Bmatrix} = 1$，若 $n > 0$ 则 $\begin{Bmatrix} n \\ 0 \end{Bmatrix} = 0$。

状态设计与算法推导

在 NOIP 实战中，对于斯特林数这种具备明显二维依存特征的计数，通常采用动态规划二维填表法处理。

1. 第二类斯特林数状态推导逻辑分析

考虑第 $n$ 个元素（新加入元素）的去向：

独立成集：该元素单独占据一个新集合。此时需要前 $n-1$ 个元素凑出 $k-1$ 个集合，方案数为 $\begin{Bmatrix} n-1 \\ k-1 \end{Bmatrix}$。
融入旧集：新元素强行塞入已经存在的 $k$ 个集合中的某一个。由于集合有区别（因为内部元素不同），因此它有 $k$ 种塞入策略。方案数为 $k \times \begin{Bmatrix} n-1 \\ k \end{Bmatrix}$。利用加法原理，两者相加即完成状态转移。

2. 第一类斯特林数状态推导逻辑分析

考虑第 $n$ 个元素在圆排列中的去向：

独立成环：自成一个单元素环。方案数为 $\begin{bmatrix} n-1 \\ k-1 \end{bmatrix}$。
插入旧环：新元素插入到已有的 $k$ 个圆排列中。它可以插入到任意一个已有元素的左侧（或右侧），由于前驱共有 $n-1$ 个元素，故有 $n-1$ 个插入位置。方案数为 $(n-1) \times \begin{bmatrix} n-1 \\ k \end{bmatrix}$。

C++ 标准源码

#include <iostream>
#include <vector>

const int MOD = 1000000007;
const int MAXN = 2000;

long long catalan[MAXN + 5];
long long S2[MAXN + 5][MAXN + 5];
long long S1[MAXN + 5][MAXN + 5];

// 预处理卡特兰数线性递推
void init_catalan(int n) {
    catalan[0] = 1;
    catalan[1] = 1;
    // 借助费马小定理求分母逆元进行单点线性推导
    auto quick_power = [](long long base, long long exp) {
        long long res = 1;
        while (exp > 0) {
            if (exp & 1) res = (res * base) % MOD;
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return res;
    };

    for (int i = 2; i <= n; ++i) {
        long long inv = quick_power(i + 1, MOD - 2);
        catalan[i] = (4 * i - 2) * catalan[i - 1] % MOD * inv % MOD;
    }
}

// 预处理两类斯特林数矩阵
void init_stirling(int n) {
    S1[0][0] = 1;
    S2[0][0] = 1;

    for (int i = 1; i <= n; ++i) {
        S1[i][0] = 0;
        S2[i][0] = 0;
        for (int j = 1; j <= i; ++j) {
            // 第一类斯特林数状态转移
            S1[i][j] = (S1[i - 1][j - 1] + (i - 1) * S1[i - 1][j]) % MOD;
            // 第二类斯特林数状态转移
            S2[i][j] = (S2[i - 1][j - 1] + j * S2[i - 1][j]) % MOD; // 致命点：此处乘数是 j 而非 i-1
        }
    }
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    init_catalan(MAXN);
    init_stirling(MAXN);

    int n, k;
    if (std::cin >> n >> k) {
        if (n <= MAXN && k <= n) {
            std::cout << "Catalan(" << n << ") = " << catalan[n] << "\n";
            std::cout << "S1(" << n << "," << k << ") = " << S1[n][k] << "\n";
            std::cout << "S2(" << n << "," << k << ") = " << S2[n][k] << "\n";
        }
    }
    return 0;
}

NOIP 实战避坑指南

混淆一类与二类斯特林数的转移乘数 选手在紧张时经常会记错乘数。第一类乘的是整个前驱规模 $(i - 1)$（代表可插入的位置数），而第二类乘的是当前目标集合数 $j$（代表可选择的合集数）。一旦两数记反，递推表的数据特征会发生根本性突变。
卡特兰数线性递推中忘记求逆元导致整除截断 在公式 $H_n = \frac{4n-2}{n+1} H_{n-1}$ 中，涉及分子除以 $n+1$。在模意义下，直接使用 C++ 的 / 运算符相当于对中间结果直接抹去小数，而非取模除法。必须老老实实通过快速幂算出 $(n + 1)$ 在模 $MOD$ 意义下的逆元再执行乘法。

经典 NOIP/洛谷真题

1. 洛谷 P3941 入阵曲 / 变式洛谷 P5386 [CERC2018] Game on Tree (涉及第二类斯特林数)

题意描述：求将 $n$ 个不同的球放入 $m$ 个相同的盒子里，且没有空盒子的方案数。
问题本质：纯粹的第二类斯特林数定义落地。
核心解题思路：因为球不同、盒子无区别，且约束不能有空盒子，这完美契合了第二类斯特林数 $\begin{Bmatrix} n \\ m \end{Bmatrix}$ 的基本模型。如果题目变式为“盒子有区别”，只需在算出的斯特林数基础上乘以盒子的全排列系数 $m!$ 即可。

2. 洛谷 P1655 小朋友的球

题意描述：$N$ 个不同的球放入 $M$ 个相同的盒子里。求方案数。无空盒限制，但数据范围需要高精度承载。
问题本质：非质数模数限制下的第二类斯特林数高精化填表。
核心解题思路：若题目明确允许有空盒，我们只需枚举真实生效的盒子数量 $k$（从 $1 \to M$ 循环），总方案数即为 $\sum_{k=1}^M \begin{Bmatrix} N \\ k \end{Bmatrix}$。若数据没有给出模数且范围较大，需将上文源码中的转移方程改造为高精度加法和高精度单精度乘法进行递推。