在信息学奥林匹克竞赛（NOI/NOIP/CSP等）中，组合数学和递推数列是常见的重要考点。掌握常见数列的数学背景、递推性质以及高效的算法实现，是解决许多计数类、动态规划类问题的关键。

以下为您整理一份关于**信奥中常见数列**的专题讲义。

---

# 信奥核心数列专题讲义

## 目录
1. **斐波那契数列 (Fibonacci Sequence)** —— 递推与矩阵乘法加速
2. **卡特兰数 (Catalan Numbers)** —— 经典组合计数与括号匹配
3. **第二类斯特林数 (Stirling Numbers of the Second Kind)** —— 集合划分问题
4. **错排数列 (Derangement Sequence)** —— 元素失配问题
5. **杨辉三角与组合数 (Pascal's Triangle)** —— 组合计数的基础

---

## 1. 斐波那契数列 (Fibonacci Sequence)

### 1.1 背景与特点
斐波那契数列是最基础的递推数列。在数论、黄金分割、动态规划中都有广泛应用。
*   **经典场景**：爬楼梯问题（每次只能跨1级或2级步）、铺砖问题、黄金分割逼近。
*   **核心性质**：
    1.  邻项之比：$\lim\_{n \to \infty} \frac{F\_n}{F\_{n+1}} = \frac{\sqrt{5}-1}{2}$ （黄金分割）。
    2.  求和公式：$\sum\_{i=1}^n F\_i = F\_{n+2} - 1$。
    3.  平方和性质：$\sum\_{i=1}^n F\_i^2 = F\_n F\_{n+1}$。

### 1.2 公式
*   **递推公式**：  
    $$F\_0 = 0, \quad F\_1 = 1$$
    $$F\_n = F\_{n-1} + F\_{n-2} \quad (n \ge 2)$$
*   **通项公式**（特征根法求得）：  
    $$F\_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right]$$
    *注：由于实数精度问题，程序中极少直接使用通项公式计算高项。*
*   **矩阵乘法公式**（适合 $n \le 10^{18}$ 级别的快速求解）：
    $$\begin{bmatrix} F\_n \\\ F\_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\\ 1 & 0 \end{bmatrix} \begin{bmatrix} F\_{n-1} \\\ F\_{n-2} \end{bmatrix} \implies \begin{bmatrix} F\_n \\\ F\_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\\ 1 & 0 \end{bmatrix}^{n-1} \begin{bmatrix} F\_1 \\\ F\_0 \end{bmatrix}$$

### 1.3 C++ 编程实现
在信奥中，由于 $F\_n$ 增长极快，通常会要求对一个大质数（如 $10^9+7$）取模。下面给出使用**矩阵快速幂**在 $O(\log n)$ 时间复杂度下求解 $F\_n$ 的代码。

```cpp
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

// 定义2x2矩阵乘法
struct Matrix {
    long long mat[2][2];
    Matrix() {
        mat[0][0] = mat[0][1] = mat[1][0] = mat[1][1] = 0;
    }
};

Matrix multiply(const Matrix& A, const Matrix& B) {
    Matrix C;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
            }
        }
    }
    return C;
}

// 矩阵快速幂
Matrix power(Matrix A, long long p) {
    Matrix res;
    res.mat[0][0] = 1; res.mat[1][1] = 1; // 单位矩阵
    while (p > 0) {
        if (p & 1) res = multiply(res, A);
        A = multiply(A, A);
        p >>= 1;
    }
    return res;
}

long long get_fibonacci(long long n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    Matrix T;
    T.mat[0][0] = 1; T.mat[0][1] = 1;
    T.mat[1][0] = 1; T.mat[1][1] = 0;
    
    Matrix T_pow = power(T, n - 1);
    // [F_n, F_{n-1}]^T = T^{n-1} * [F_1, F_0]^T = T^{n-1} * [1, 0]^T
    return T_pow.mat[0][0]; // 对应 F_n
}

int main() {
    long long n;
    if (cin >> n) {
        cout << get_fibonacci(n) << endl;
    }
    return 0;
}
```

---

## 2. 卡特兰数 (Catalan Numbers)

### 2.1 背景与特点
卡特兰数是组合数学中极为重要的计数数列。
*   **经典场景**：
    1.  **括号序列**：由 $n$ 个左括号和 $n$ 个右括号组成的所有合法的括号匹配序列方案数。
    2.  **出栈序列**：一个足够大的栈，入栈序列为 $1, 2, \dots, n$，不同的出栈序列方案数。
    3.  **二叉树计数**：$n$ 个节点可以构造出多少种不同形态的二叉树。
    4.  **多边形剖分**：将一个凸 $n+2$ 边形通过不相交的对角线剖分成三角形的方案数。
    5.  **网格路径**：在 $n \times n$ 网格中，从左下角 $(0,0)$ 走到右上角 $(n,n)$，且不穿过主对角线 $y=x$ 的路径数。

### 2.2 公式
设卡特兰数的第 $n$ 项为 $H\_n$（通常约定 $H\_0 = 1$）：
*   **乘法通项公式**：
    $$H\_n = \frac{1}{n+1} \binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n-1}$$
*   **递推公式（加法式，即分裂结构描述）**：
    $$H\_n = \sum\_{i=0}^{n-1} H\_i H\_{n-1-i} \quad (H\_0 = 1)$$
*   **线性递推公式（高效计算）**：
    $$H\_n = \frac{4n-2}{n+1} H\_{n-1}$$

### 2.3 C++ 编程实现
利用线性递推公式，结合乘法逆元（在取模意义下代替除法），可以在 $O(n)$ 的时间复杂度内求出前 $n$ 个卡特兰数。

```cpp
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

// 快速幂求乘法逆元
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, MOD - 2); // 费马小定理
}

// O(N) 求解前 N 项卡特兰数
vector<long long> get_catalan(int n) {
    vector<long long> H(n + 1);
    H[0] = 1;
    for (int i = 1; i <= n; ++i) {
        // H_i = H_{i-1} * (4i - 2) / (i + 1)
        long long numerator = (4 * i - 2) * H[i - 1] % MOD;
        long long denominator = modInverse(i + 1);
        H[i] = numerator * denominator % MOD;
    }
    return H;
}

int main() {
    int n;
    if (cin >> n) {
        vector<long long> H = get_catalan(n);
        cout << H[n] << endl;
    }
    return 0;
}
```

---

## 3. 第二类斯特林数 (Stirling Numbers of the Second Kind)

### 3.1 背景与特点
第二类斯特林数，记为 $S(n, k)$ 或 $\begin{Bmatrix} n \\ k \end{Bmatrix}$。
*   **经典场景**：
    *   将 $n$ 个**有区别**（不同）的球，放入 $k$ 个**无区别**（相同）的盒子里，且**每个盒子不能为空**的方案数。
*   **扩展应用（球盒模型）**：
    *   如果盒子也是“有区别”的，则方案数为 $k! \cdot S(n, k)$。

### 3.2 公式
*   **递推公式**：
    $$S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k)$$
    *   **边界条件**：$S(n, n) = 1$，$S(n, 1) = 1$，且对于 $k > n$ 或 $k = 0$，有 $S(n, k) = 0$。
    *   *递推意义解释*：考虑第 $n$ 个球：
        1. 它独自占一个新盒子，剩下 $n-1$ 个球放入 $k-1$ 个盒子中：$S(n-1, k-1)$；
        2. 它加入已经建好的 $k$ 个盒子中的任意一个（有 $k$ 种选择），剩下 $n-1$ 个球已分入 $k$ 个盒子：$k \cdot S(n-1, k)$。

### 3.3 C++ 编程实现
利用动态规划（DP）可以在 $O(n \cdot k)$ 的时间复杂度内求出 $S(n, k)$。若有更高级的需求，可以通过卷积（NTT）在 $O(n \log n)$ 内求解单行。这里介绍信奥中最常用的 DP 实现。

```cpp
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

// O(N*K) 动态规划实现
long long get_stirling_second(int n, int k) {
    if (k > n || k < 0) return 0;
    
    // DP 状态转移数组，可使用滚动数组优化空间
    vector<vector<long long>> S(n + 1, vector<long long>(k + 1, 0));
    
    for (int i = 1; i <= n; ++i) {
        S[i][1] = 1; // 放入1个盒子只有1种放法
        if (i <= k) S[i][i] = 1; // 放入i个盒子只有1种放法
    }

for (int i = 2; i <= n; ++i) {
        for (int j = 2; j <= min(i - 1, k); ++j) {
            S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j]) % MOD;
        }
    }
    
    return S[n][k];
}

int main() {
    int n, k;
    if (cin >> n >> k) {
        cout << get_stirling_second(n, k) << endl;
    }
    return 0;
}
```

---

## 4. 错排数列 (Derangement Sequence)

### 4.1 背景与特点
错排问题（Derangement）是关于排序列的计数问题。
*   **经典场景**：有 $n$ 封写好收件人名字的信和 $n$ 个写好收件人地址的信封。问：将信装入信封，使得**每一封信都装错**（没有一封信送对人）的装法有多少种？
*   **核心性质**：
    *   错排数列前几项：$D\_1 = 0, D\_2 = 1, D\_3 = 2, D\_4 = 9, D\_5 = 44$。

### 4.2 公式
*   **递推公式**：
    $$D\_1 = 0, \quad D\_2 = 1$$
    $$D\_n = (n-1) (D\_{n-1} + D\_{n-2}) \quad (n \ge 3)$$
    *   *递推意义解释*：假设第 $n$ 个元素排在位置 $k$（$k \ne n$，共有 $n-1$ 种选择）：
        1. 若元素 $k$ 刚好排在位置 $n$，此时第 $n$ 和第 $k$ 项完成了交换，其余 $n-2$ 个元素错排，方案数为 $D\_{n-2}$；
        2. 若元素 $k$ 不排在位置 $n$，可以将位置 $n$ 视作元素 $k$ 原来的“禁位”，此时相当于这 $n-1$ 个元素进行错排，方案数为 $D\_{n-1}$。
*   **通项公式**（通过容斥原理可得）：
    $$D\_n = n! \sum\_{i=2}^n \frac{(-1)^i}{i!}$$

### 4.3 C++ 编程实现
利用递推公式，可以在 $O(n)$ 时间复杂度和 $O(1)$ 空间复杂度内求出第 $n$ 个错排数。

```cpp
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

long long get_derangement(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 1;
    
    long long dp1 = 0; // D_1
    long long dp2 = 1; // D_2
    long long dpn = 0;
    
    for (int i = 3; i <= n; ++i) {
        dpn = (i - 1) * (dp1 + dp2) % MOD;
        dp1 = dp2;
        dp2 = dpn;
    }
    return dpn;
}

int main() {
    int n;
    if (cin >> n) {
        cout << get_derangement(n) << endl;
    }
    return 0;
}
```

---

## 5. 杨辉三角与组合数 (Pascal's Triangle & Binomial Coefficients)

### 5.1 背景与特点
杨辉三角是二项式系数在三角形中的几何排列，是中国古代数学的杰出成果，也是现代信奥组合计数的基础。
*   **经典场景**：
    *   从 $n$ 个不同元素中无顺序地取出 $k$ 个元素的方案数 $\binom{n}{k}$ （或 $C\_n^k$）。
    *   多项式定理中 $(x+y)^n$ 的展开系数。
*   **核心性质**：
    *   第 $n$ 行的所有元素之和为 $2^n$。
    *   对称性：$\binom{n}{k} = \binom{n}{n-k}$。

### 5.2 公式
*   **加法递推公式（杨辉三角的核心）**：
    $$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$
    *边界条件*：$\binom{n}{0} = \binom{n}{n} = 1$。
*   **阶乘定义式**：
    $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

### 5.3 C++ 编程实现
在信奥中，计算组合数有两种最常用的方法：
1.  **动态规划递推**：适合 $n, k \le 2000$ 左右的小规模且需要频繁查询的场景（$O(n^2)$ 预处理，$O(1)$ 查询）。
2.  **逆元法**：适合 $n, k \le 10^6$ 级别的单次或多次查询（$O(n)$ 预处理阶乘与逆元，$O(1)$ 计算单项）。

#### 方法一：二维 DP（杨辉三角递推，无需逆元，适用于各种模数）
```cpp
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 2005;
const int MOD = 1e9 + 7;
long long C[MAXN][MAXN];

// 预处理杨辉三角
void init_pascal() {
    for (int i = 0; i < MAXN; ++i) {
        C[i][0] = 1; // 边界
        for (int j = 1; j <= i; ++j) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
    }
}

int main() {
    init_pascal();
    int n, k;
    if (cin >> n >> k) {
        if (k <= n) cout << C[n][k] << endl;
        else cout << 0 << endl;
    }
    return 0;
}
```

#### 方法二：阶乘与逆元预处理（适用于大规模数据，模数需为质数）
```cpp
#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;

long long fact[MAXN];
long long invFact[MAXN];

// 快速幂
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 预处理阶乘和逆元
void init_factorial() {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    // 计算最后一个的逆元，再逆向推导其余逆元，可将复杂度降至线性 O(N)
    invFact[MAXN - 1] = power(fact[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 1; --i) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }
}

// O(1) 查询组合数
long long get_combination(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

int main() {
    init_factorial();
    int n, k;
    if (cin >> n >> k) {
        cout << get_combination(n, k) << endl;
    }
    return 0;
}
```

---

## 结语

在信息学竞赛中，数学数列的考察往往不会直接给出名字，而是隐藏在具体的业务场景（如：路径规划、物品分组、排列限制）中。熟练掌握以上几种数列的数学模型和递推式，能够帮助我们在面对问题时快速进行**模型转化**，从而设计出时空复杂度双优的算法。

以下为您整理一份关于信奥中常见数列的专题讲义。

信奥核心数列专题讲义

斐波那契数列 (Fibonacci Sequence) —— 递推与矩阵乘法加速
卡特兰数 (Catalan Numbers) —— 经典组合计数与括号匹配
第二类斯特林数 (Stirling Numbers of the Second Kind) —— 集合划分问题
错排数列 (Derangement Sequence) —— 元素失配问题
杨辉三角与组合数 (Pascal's Triangle) —— 组合计数的基础

1. 斐波那契数列 (Fibonacci Sequence)

1.1 背景与特点

斐波那契数列是最基础的递推数列。在数论、黄金分割、动态规划中都有广泛应用。 * 经典场景：爬楼梯问题（每次只能跨1级或2级步）、铺砖问题、黄金分割逼近。 * 核心性质： 1. 邻项之比：$\lim_{n \to \infty} \frac{F_n}{F_{n+1}} = \frac{\sqrt{5}-1}{2}$ （黄金分割）。 2. 求和公式：$\sum_{i=1}^n F_i = F_{n+2} - 1$。 3. 平方和性质：$\sum_{i=1}^n F_i^2 = F_n F_{n+1}$。

1.2 公式

递推公式：
$$F_0 = 0, \quad F_1 = 1$$ $$F_n = F_{n-1} + F_{n-2} \quad (n \ge 2)$$
通项公式（特征根法求得）：
$$F_n = \frac{1}{\sqrt{5}} \left[ \left(\frac{1+\sqrt{5}}{2}\right)^n - \left(\frac{1-\sqrt{5}}{2}\right)^n \right]$$ 注：由于实数精度问题，程序中极少直接使用通项公式计算高项。
矩阵乘法公式（适合 $n \le 10^{18}$ 级别的快速求解）： $$\begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} \begin{bmatrix} F_{n-1} \\ F_{n-2} \end{bmatrix} \implies \begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1} \begin{bmatrix} F_1 \\ F_0 \end{bmatrix}$$

1.3 C++ 编程实现

在信奥中，由于 $F_n$ 增长极快，通常会要求对一个大质数（如 $10^9+7$）取模。下面给出使用矩阵快速幂在 $O(\log n)$ 时间复杂度下求解 $F_n$ 的代码。

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

// 定义2x2矩阵乘法
struct Matrix {
    long long mat[2][2];
    Matrix() {
        mat[0][0] = mat[0][1] = mat[1][0] = mat[1][1] = 0;
    }
};

Matrix multiply(const Matrix& A, const Matrix& B) {
    Matrix C;
    for (int i = 0; i < 2; ++i) {
        for (int j = 0; j < 2; ++j) {
            for (int k = 0; k < 2; ++k) {
                C.mat[i][j] = (C.mat[i][j] + A.mat[i][k] * B.mat[k][j]) % MOD;
            }
        }
    }
    return C;
}

// 矩阵快速幂
Matrix power(Matrix A, long long p) {
    Matrix res;
    res.mat[0][0] = 1; res.mat[1][1] = 1; // 单位矩阵
    while (p > 0) {
        if (p & 1) res = multiply(res, A);
        A = multiply(A, A);
        p >>= 1;
    }
    return res;
}

long long get_fibonacci(long long n) {
    if (n == 0) return 0;
    if (n == 1) return 1;
    Matrix T;
    T.mat[0][0] = 1; T.mat[0][1] = 1;
    T.mat[1][0] = 1; T.mat[1][1] = 0;

    Matrix T_pow = power(T, n - 1);
    // [F_n, F_{n-1}]^T = T^{n-1} * [F_1, F_0]^T = T^{n-1} * [1, 0]^T
    return T_pow.mat[0][0]; // 对应 F_n
}

int main() {
    long long n;
    if (cin >> n) {
        cout << get_fibonacci(n) << endl;
    }
    return 0;
}

2. 卡特兰数 (Catalan Numbers)

2.1 背景与特点

卡特兰数是组合数学中极为重要的计数数列。 * 经典场景： 1. 括号序列：由 $n$ 个左括号和 $n$ 个右括号组成的所有合法的括号匹配序列方案数。 2. 出栈序列：一个足够大的栈，入栈序列为 $1, 2, \dots, n$，不同的出栈序列方案数。 3. 二叉树计数：$n$ 个节点可以构造出多少种不同形态的二叉树。 4. 多边形剖分：将一个凸 $n+2$ 边形通过不相交的对角线剖分成三角形的方案数。 5. 网格路径：在 $n \times n$ 网格中，从左下角 $(0,0)$ 走到右上角 $(n,n)$，且不穿过主对角线 $y=x$ 的路径数。

2.2 公式

设卡特兰数的第 $n$ 项为 $H_n$（通常约定 $H_0 = 1$）： * 乘法通项公式： $$H_n = \frac{1}{n+1} \binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n-1}$$ * 递推公式（加法式，即分裂结构描述）： $$H_n = \sum_{i=0}^{n-1} H_i H_{n-1-i} \quad (H_0 = 1)$$ * 线性递推公式（高效计算）： $$H_n = \frac{4n-2}{n+1} H_{n-1}$$

2.3 C++ 编程实现

利用线性递推公式，结合乘法逆元（在取模意义下代替除法），可以在 $O(n)$ 的时间复杂度内求出前 $n$ 个卡特兰数。

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

// 快速幂求乘法逆元
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

long long modInverse(long long n) {
    return power(n, MOD - 2); // 费马小定理
}

// O(N) 求解前 N 项卡特兰数
vector<long long> get_catalan(int n) {
    vector<long long> H(n + 1);
    H[0] = 1;
    for (int i = 1; i <= n; ++i) {
        // H_i = H_{i-1} * (4i - 2) / (i + 1)
        long long numerator = (4 * i - 2) * H[i - 1] % MOD;
        long long denominator = modInverse(i + 1);
        H[i] = numerator * denominator % MOD;
    }
    return H;
}

int main() {
    int n;
    if (cin >> n) {
        vector<long long> H = get_catalan(n);
        cout << H[n] << endl;
    }
    return 0;
}

3. 第二类斯特林数 (Stirling Numbers of the Second Kind)

3.1 背景与特点

第二类斯特林数，记为 $S(n, k)$ 或 $\begin{Bmatrix} n \ k \end{Bmatrix}$。 * 经典场景： * 将 $n$ 个有区别（不同）的球，放入 $k$ 个无区别（相同）的盒子里，且每个盒子不能为空的方案数。 * 扩展应用（球盒模型）： * 如果盒子也是“有区别”的，则方案数为 $k! \cdot S(n, k)$。

3.2 公式

递推公式： $$S(n, k) = S(n-1, k-1) + k \cdot S(n-1, k)$$
- 边界条件：$S(n, n) = 1$，$S(n, 1) = 1$，且对于 $k > n$ 或 $k = 0$，有 $S(n, k) = 0$。
- 递推意义解释：考虑第 $n$ 个球：
  1. 它独自占一个新盒子，剩下 $n-1$ 个球放入 $k-1$ 个盒子中：$S(n-1, k-1)$；
  2. 它加入已经建好的 $k$ 个盒子中的任意一个（有 $k$ 种选择），剩下 $n-1$ 个球已分入 $k$ 个盒子：$k \cdot S(n-1, k)$。

3.3 C++ 编程实现

利用动态规划（DP）可以在 $O(n \cdot k)$ 的时间复杂度内求出 $S(n, k)$。若有更高级的需求，可以通过卷积（NTT）在 $O(n \log n)$ 内求解单行。这里介绍信奥中最常用的 DP 实现。

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

// O(N*K) 动态规划实现
long long get_stirling_second(int n, int k) {
    if (k > n || k < 0) return 0;

    // DP 状态转移数组，可使用滚动数组优化空间
    vector<vector<long long>> S(n + 1, vector<long long>(k + 1, 0));

    for (int i = 1; i <= n; ++i) {
        S[i][1] = 1; // 放入1个盒子只有1种放法
        if (i <= k) S[i][i] = 1; // 放入i个盒子只有1种放法
    }

    for (int i = 2; i <= n; ++i) {
        for (int j = 2; j <= min(i - 1, k); ++j) {
            S[i][j] = (S[i - 1][j - 1] + j * S[i - 1][j]) % MOD;
        }
    }

    return S[n][k];
}

int main() {
    int n, k;
    if (cin >> n >> k) {
        cout << get_stirling_second(n, k) << endl;
    }
    return 0;
}

4. 错排数列 (Derangement Sequence)

4.1 背景与特点

错排问题（Derangement）是关于排序列的计数问题。 * 经典场景：有 $n$ 封写好收件人名字的信和 $n$ 个写好收件人地址的信封。问：将信装入信封，使得每一封信都装错（没有一封信送对人）的装法有多少种？ * 核心性质： * 错排数列前几项：$D_1 = 0, D_2 = 1, D_3 = 2, D_4 = 9, D_5 = 44$。

4.2 公式

递推公式： $$D_1 = 0, \quad D_2 = 1$$ $$D_n = (n-1) (D_{n-1} + D_{n-2}) \quad (n \ge 3)$$
- 递推意义解释：假设第 $n$ 个元素排在位置 $k$（$k \ne n$，共有 $n-1$ 种选择）：
  1. 若元素 $k$ 刚好排在位置 $n$，此时第 $n$ 和第 $k$ 项完成了交换，其余 $n-2$ 个元素错排，方案数为 $D_{n-2}$；
  2. 若元素 $k$ 不排在位置 $n$，可以将位置 $n$ 视作元素 $k$ 原来的“禁位”，此时相当于这 $n-1$ 个元素进行错排，方案数为 $D_{n-1}$。
通项公式（通过容斥原理可得）： $$D_n = n! \sum_{i=2}^n \frac{(-1)^i}{i!}$$

4.3 C++ 编程实现

利用递推公式，可以在 $O(n)$ 时间复杂度和 $O(1)$ 空间复杂度内求出第 $n$ 个错排数。

#include <iostream>
#include <vector>

using namespace std;

const int MOD = 1e9 + 7;

long long get_derangement(int n) {
    if (n <= 1) return 0;
    if (n == 2) return 1;

    long long dp1 = 0; // D_1
    long long dp2 = 1; // D_2
    long long dpn = 0;

    for (int i = 3; i <= n; ++i) {
        dpn = (i - 1) * (dp1 + dp2) % MOD;
        dp1 = dp2;
        dp2 = dpn;
    }
    return dpn;
}

int main() {
    int n;
    if (cin >> n) {
        cout << get_derangement(n) << endl;
    }
    return 0;
}

5. 杨辉三角与组合数 (Pascal's Triangle & Binomial Coefficients)

5.1 背景与特点

杨辉三角是二项式系数在三角形中的几何排列，是中国古代数学的杰出成果，也是现代信奥组合计数的基础。 * 经典场景： * 从 $n$ 个不同元素中无顺序地取出 $k$ 个元素的方案数 $\binom{n}{k}$ （或 $C_n^k$）。 * 多项式定理中 $(x+y)^n$ 的展开系数。 * 核心性质： * 第 $n$ 行的所有元素之和为 $2^n$。 * 对称性：$\binom{n}{k} = \binom{n}{n-k}$。

5.2 公式

加法递推公式（杨辉三角的核心）： $$\binom{n}{k} = \binom{n-1}{k} + \binom{n-1}{k-1}$$ 边界条件：$\binom{n}{0} = \binom{n}{n} = 1$。
阶乘定义式： $$\binom{n}{k} = \frac{n!}{k!(n-k)!}$$

5.3 C++ 编程实现

在信奥中，计算组合数有两种最常用的方法： 1. 动态规划递推：适合 $n, k \le 2000$ 左右的小规模且需要频繁查询的场景（$O(n^2)$ 预处理，$O(1)$ 查询）。 2. 逆元法：适合 $n, k \le 10^6$ 级别的单次或多次查询（$O(n)$ 预处理阶乘与逆元，$O(1)$ 计算单项）。

方法一：二维 DP（杨辉三角递推，无需逆元，适用于各种模数）

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 2005;
const int MOD = 1e9 + 7;
long long C[MAXN][MAXN];

// 预处理杨辉三角
void init_pascal() {
    for (int i = 0; i < MAXN; ++i) {
        C[i][0] = 1; // 边界
        for (int j = 1; j <= i; ++j) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
    }
}

int main() {
    init_pascal();
    int n, k;
    if (cin >> n >> k) {
        if (k <= n) cout << C[n][k] << endl;
        else cout << 0 << endl;
    }
    return 0;
}

方法二：阶乘与逆元预处理（适用于大规模数据，模数需为质数）

#include <iostream>
#include <vector>

using namespace std;

const int MAXN = 1e6 + 5;
const int MOD = 1e9 + 7;

long long fact[MAXN];
long long invFact[MAXN];

// 快速幂
long long power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp % 2 == 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp /= 2;
    }
    return res;
}

// 预处理阶乘和逆元
void init_factorial() {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i < MAXN; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    // 计算最后一个的逆元，再逆向推导其余逆元，可将复杂度降至线性 O(N)
    invFact[MAXN - 1] = power(fact[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 1; --i) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }
}

// O(1) 查询组合数
long long get_combination(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * invFact[k] % MOD * invFact[n - k] % MOD;
}

int main() {
    init_factorial();
    int n, k;
    if (cin >> n >> k) {
        cout << get_combination(n, k) << endl;
    }
    return 0;
}

结语

在信息学竞赛中，数学数列的考察往往不会直接给出名字，而是隐藏在具体的业务场景（如：路径规划、物品分组、排列限制）中。熟练掌握以上几种数列的数学模型和递推式，能够帮助我们在面对问题时快速进行模型转化，从而设计出时空复杂度双优的算法。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com