这是为您编写的**信奥中的排列、组合与组合数学基础讲义**。

在信息学奥林匹克竞赛中，排列组合是组合数学（Combinatorics）的核心部分。与纯数学不同，信奥不仅要求掌握公式推导，更注重**在大数据规模下的快速计算（如模运算下的 $O(1)$ 查询）**以及**算法模型（如动态规划、容斥原理等）**的结合。

---

# 信奥中的排列组合与组合数学基础讲义

## 一、 基本计数原理与概念

在解决计数问题时，一切复杂算法都基于以下两个最基础的原理。

### 1.1 两个基本原理
* **加法原理（分类计数）**：完成一件事有 $n$ 类办法。第一类办法中有 $m\_1$ 种不同方法，第二类办法中有 $m\_2$ 种不同方法……则完成这件事共有：
  $$N = m\_1 + m\_2 + \dots + m\_n$$
  *(特点：各类别相互独立，互不重合)*

* **乘法原理（分步计数）**：完成一件事需要分成 $n$ 个步骤。第一步有 $m\_1$ 种不同方法，第二步有 $m\_2$ 种不同方法……则完成这件事共有：
  $$N = m\_1 \times m\_2 \times \dots \times m\_n$$
  *(特点：各步骤连续发生，环环相扣)*

---

### 1.2 排列与组合公式

#### ① 排列（Permutation）
从 $n$ 个不同元素中取出 $m$（$m \le n$）个元素，按照一定的顺序排成一列。其排列方案数记作 $P\_n^m$（或 $A\_n^m$）：
$$P\_n^m = n(n-1)(n-2)\dots(n-m+1) = \frac{n!}{(n-m)!}$$
* **全排列**：当 $m = n$ 时，全排列方案数为 $P\_n^n = n!$。

#### ② 组合（Combination）
从 $n$ 个不同元素中取出 $m$（$m \le n$）个元素合成一组（不考虑顺序）。其组合方案数记作 $C\_n^m$（或写为 $\binom{n}{m}$）：
$$C\_n^m = \binom{n}{m} = \frac{P\_n^m}{m!} = \frac{n!}{m!(n-m)!}$$

#### ③ 组合数的两个重要性质
1. **对称性**：
   $$C\_n^m = C\_n^{n-m}$$
   *(从 $n$ 个元素中选出 $m$ 个保留，等价于选出 $n-m$ 个丢弃)*
2. **递推性（杨辉三角原理）**：
   $$C\_{n+1}^m = C\_n^m + C\_n^{m-1}$$
   *(考虑第 $n+1$ 个元素：如果不选它，则需在前 $n$ 个元素中选 $m$ 个；如果选它，则需在前 $n$ 个中选 $m-1$ 个)*

---

## 二、 计算机中组合数的求解（核心算法）

由于组合数的值随 $n, m$ 的增大呈指数级增长，信奥题目通常要求答案对一个大质数 $P$（如 $10^9+7$ 或 $998244353$）取模。针对不同的数据范围，有不同的求解方法。

### 2.1 递推法（适合 $N, M \le 5000$）
利用性质 $C\_i^j = C\_{i-1}^j + C\_{i-1}^{j-1}$ 进行动态规划。
* **时间复杂度**：$O(N^2)$ 预处理，$O(1)$ 查询。
* **优点**：无需考虑除法取模问题，适用于任何模数（包括合数）。

```cpp
const int MX = 5005;
const int MOD = 1e9 + 7;
int C[MX][MX];

void init_C() {
    for (int i = 0; i < MX; i++) {
        C[i][0] = 1; // 选 0 个的方案数均为 1
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
    }
}
```

### 2.2 乘法逆元法（适合 $N, M \le 10^6$）
当 $N$ 较大时，我们需要直接使用公式 $C\_n^m = n! \times (m!)^{-1} \times ((n-m)!)^{-1} \pmod P$。
因为公式中包含除法，我们在模运算下需要求**乘法逆元**。
若 $P$ 为质数，可利用**费马小定理**：$a^{P-2} \equiv a^{-1} \pmod P$。

* **时间复杂度**：$O(N)$ 预处理阶乘与逆元，$O(1)$ 查询。

```cpp
const int MX = 1e6 + 5;
const int MOD = 998244353;

long long fact[MX];    // 阶乘数组
long long invFact[MX]; // 阶乘的逆元数组

// 快速幂
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 getInverse(long long n) {
    return power(n, MOD - 2);
}

// 线性预处理阶乘和阶乘逆元
void init() {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i < MX; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    // 先求出最大阶乘的逆元
    invFact[MX - 1] = getInverse(fact[MX - 1]);
    // 逆向递推：1/(i-1)! = 1/i! * i
    for (int i = MX - 2; i >= 1; i--) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }
}

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

### 2.3 卢卡斯定理（Lucas' Theorem，适合 $N, M \le 10^{18}$ 且 $P \le 10^5$）
如果 $n, m$ 的范围非常巨大，但模数 $P$ 是一个较小的质数，我们可以使用**卢卡斯定理**将大组合数化简：
$$\binom{n}{m} \equiv \binom{\lfloor n/P \rfloor}{\lfloor m/P \rfloor} \cdot \binom{n \bmod P}{m \bmod P} \pmod P$$
这是一个递归过程，递归边界是 $n < P$ 且 $m < P$，此时直接用普通的阶乘方法计算。

```cpp
long long lucas(long long n, long long m, long long p) {
    if (m == 0) return 1;
    return getC(n % p, m % p) * lucas(n / p, m / p, p) % p;
}
```

---

## 三、 经典组合计数模型

在信奥中，题目常常不会直白地给出排列组合，而是通过某种实际场景进行包装。以下是三种最基础且最常考的组合数学模型。

### 3.1 隔板法（Stars and Bars）
**问题描述**：将 $n$ 个相同的球放入 $k$ 个不同的盒子里，每个盒子至少放一个球，求方案数。
* **模型分析**：想象有 $n$ 个球排成一排，它们之间有 $n-1$ 个空隙。放入 $k$ 个盒子，相当于在这些空隙中插入 $k-1$ 块隔板，将其分成 $k$ 部分。
* **公式**：
  $$\text{方案数} = C\_{n-1}^{k-1}$$
* **变形（允许有空盒子）**：如果每个盒子可以为空，相当于将 $n$ 个球和 $k$ 个盒子的“名额”混合在一起，公式转化为：
  $$\text{方案数} = C\_{n+k-1}^{k-1}$$

---

### 3.2 错排数（Derangements）
**问题描述**：将 $n$ 个写有 $1 \sim n$ 的球放入标号为 $1 \sim n$ 的盒子中，使得每个球的标号与其所在的盒子标号都不相同，求方案数 $D\_n$。
* **递推关系**：
  假设前 $n-1$ 个球已完成错排。当加入第 $n$ 个球时：
  1. 如果它与前面某球 $i$（有 $n-1$ 种选择）交换位置，且其余 $n-2$ 个球构成错排，此时有 $(n-1) \cdot D\_{n-2}$ 种情况。
  2. 如果它与前面某球 $i$ 交换，但其余 $n-1$ 个球已经构成错排，此时有 $(n-1) \cdot D\_{n-1}$ 种情况。
* **公式**：
  $$D\_1 = 0, \quad D\_2 = 1$$
  $$D\_n = (n-1)(D\_{n-1} + D\_{n-2}) \quad (n \ge 3)$$

---

### 3.3 卡特兰数（Catalan Numbers）
**应用场景**：
1. 长度为 $2n$ 的合法括号序列数量。
2. $n$ 个节点的二叉树不同形态数量。
3. 出栈序列数（$n$ 个数依次入栈，求可能的出栈序列数）。
4. 在网格图上，从 $(0,0)$ 走到 $(n,n)$ 且不穿过对角线 $y = x$ 的路径数。

* **常用计算公式**：
  $$H\_n = \frac{C\_{2n}^n}{n+1} = C\_{2n}^n - C\_{2n}^{n-1}$$
* **递推式**：
  $$H\_0 = 1, \quad H\_n = \sum\_{i=0}^{n-1} H\_i H\_{n-1-i}$$

---

## 附录：数列的基础性质与信奥扩展

在处理排列组合和动态规划时，常常会伴随着**等差数列**与**等比数列**的求和。

### 1. 等差数列（Arithmetic Progression）
* 通项公式：$a\_n = a\_1 + (n-1)d$
* 求和公式：$S\_n = \frac{a\_1 + a\_n}{2} \cdot n = n a\_1 + \frac{n(n-1)}{2}d$

### 2. 等比数列（Geometric Progression）
* 通项公式：$a\_n = a\_1 q^{n-1}$
* 求和公式（当 $q \neq 1$ 时）：$S\_n = a\_1 \frac{1-q^n}{1-q}$

**信奥考点：等比数列模意义下求和**
当需要在模 $P$ 意义下求等比数列和 $S\_n$ 时，若 $1-q$ 与 $P$ 互质，可直接用逆元计算：
$$S\_n \equiv a\_1 \cdot (1-q^n) \cdot (1-q)^{-1} \pmod P$$
若 $1-q$ 与 $P$ 不互质（或者 $P$ 不是质数），可以使用**分治法（Divide and Conquer）**在 $O(\log n)$ 内计算：
$$S\_n = \begin{cases} 
a\_1 & n=1 \\
(1 + q^{n/2}) S\_{n/2} & n \text{ 为偶数} \\
(1 + q^{(n-1)/2}) S\_{(n-1)/2} + a\_1 q^{n-1} & n \text{ 为奇数}
\end{cases}$$

这是为您编写的信奥中的排列、组合与组合数学基础讲义。

在信息学奥林匹克竞赛中，排列组合是组合数学（Combinatorics）的核心部分。与纯数学不同，信奥不仅要求掌握公式推导，更注重在大数据规模下的快速计算（如模运算下的 $O(1)$ 查询）以及算法模型（如动态规划、容斥原理等）的结合。

信奥中的排列组合与组合数学基础讲义

一、基本计数原理与概念

在解决计数问题时，一切复杂算法都基于以下两个最基础的原理。

1.1 两个基本原理

加法原理（分类计数）：完成一件事有 $n$ 类办法。第一类办法中有 $m_1$ 种不同方法，第二类办法中有 $m_2$ 种不同方法……则完成这件事共有： $$N = m_1 + m_2 + \dots + m_n$$ (特点：各类别相互独立，互不重合)
乘法原理（分步计数）：完成一件事需要分成 $n$ 个步骤。第一步有 $m_1$ 种不同方法，第二步有 $m_2$ 种不同方法……则完成这件事共有： $$N = m_1 \times m_2 \times \dots \times m_n$$ (特点：各步骤连续发生，环环相扣)

1.2 排列与组合公式

① 排列（Permutation）

从 $n$ 个不同元素中取出 $m$（$m \le n$）个元素，按照一定的顺序排成一列。其排列方案数记作 $P_n^m$（或 $A_n^m$）： $$P_n^m = n(n-1)(n-2)\dots(n-m+1) = \frac{n!}{(n-m)!}$$ * 全排列：当 $m = n$ 时，全排列方案数为 $P_n^n = n!$。

② 组合（Combination）

从 $n$ 个不同元素中取出 $m$（$m \le n$）个元素合成一组（不考虑顺序）。其组合方案数记作 $C_n^m$（或写为 $\binom{n}{m}$）： $$C_n^m = \binom{n}{m} = \frac{P_n^m}{m!} = \frac{n!}{m!(n-m)!}$$

③ 组合数的两个重要性质

对称性： $$C_n^m = C_n^{n-m}$$ (从 $n$ 个元素中选出 $m$ 个保留，等价于选出 $n-m$ 个丢弃)
递推性（杨辉三角原理）： $$C_{n+1}^m = C_n^m + C_n^{m-1}$$ (考虑第 $n+1$ 个元素：如果不选它，则需在前 $n$ 个元素中选 $m$ 个；如果选它，则需在前 $n$ 个中选 $m-1$ 个)

二、计算机中组合数的求解（核心算法）

2.1 递推法（适合 $N, M \le 5000$）

利用性质 $C_i^j = C_{i-1}^j + C_{i-1}^{j-1}$ 进行动态规划。 * 时间复杂度：$O(N^2)$ 预处理，$O(1)$ 查询。 * 优点：无需考虑除法取模问题，适用于任何模数（包括合数）。

const int MX = 5005;
const int MOD = 1e9 + 7;
int C[MX][MX];

void init_C() {
    for (int i = 0; i < MX; i++) {
        C[i][0] = 1; // 选 0 个的方案数均为 1
        for (int j = 1; j <= i; j++) {
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
        }
    }
}

2.2 乘法逆元法（适合 $N, M \le 10^6$）

当 $N$ 较大时，我们需要直接使用公式 $C_n^m = n! \times (m!)^{-1} \times ((n-m)!)^{-1} \pmod P$。因为公式中包含除法，我们在模运算下需要求乘法逆元。若 $P$ 为质数，可利用费马小定理：$a^{P-2} \equiv a^{-1} \pmod P$。

时间复杂度：$O(N)$ 预处理阶乘与逆元，$O(1)$ 查询。

const int MX = 1e6 + 5;
const int MOD = 998244353;

long long fact[MX];    // 阶乘数组
long long invFact[MX]; // 阶乘的逆元数组

// 快速幂
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 getInverse(long long n) {
    return power(n, MOD - 2);
}

// 线性预处理阶乘和阶乘逆元
void init() {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i < MX; i++) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }
    // 先求出最大阶乘的逆元
    invFact[MX - 1] = getInverse(fact[MX - 1]);
    // 逆向递推：1/(i-1)! = 1/i! * i
    for (int i = MX - 2; i >= 1; i--) {
        invFact[i] = (invFact[i + 1] * (i + 1)) % MOD;
    }
}

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

2.3 卢卡斯定理（Lucas' Theorem，适合 $N, M \le 10^{18}$ 且 $P \le 10^5$）

如果 $n, m$ 的范围非常巨大，但模数 $P$ 是一个较小的质数，我们可以使用卢卡斯定理将大组合数化简： $$\binom{n}{m} \equiv \binom{\lfloor n/P \rfloor}{\lfloor m/P \rfloor} \cdot \binom{n \bmod P}{m \bmod P} \pmod P$$ 这是一个递归过程，递归边界是 $n < P$ 且 $m < P$，此时直接用普通的阶乘方法计算。

long long lucas(long long n, long long m, long long p) {
    if (m == 0) return 1;
    return getC(n % p, m % p) * lucas(n / p, m / p, p) % p;
}

三、经典组合计数模型

在信奥中，题目常常不会直白地给出排列组合，而是通过某种实际场景进行包装。以下是三种最基础且最常考的组合数学模型。

3.1 隔板法（Stars and Bars）

问题描述：将 $n$ 个相同的球放入 $k$ 个不同的盒子里，每个盒子至少放一个球，求方案数。 * 模型分析：想象有 $n$ 个球排成一排，它们之间有 $n-1$ 个空隙。放入 $k$ 个盒子，相当于在这些空隙中插入 $k-1$ 块隔板，将其分成 $k$ 部分。 * 公式： $$\text{方案数} = C_{n-1}^{k-1}$$ * 变形（允许有空盒子）：如果每个盒子可以为空，相当于将 $n$ 个球和 $k$ 个盒子的“名额”混合在一起，公式转化为： $$\text{方案数} = C_{n+k-1}^{k-1}$$

3.2 错排数（Derangements）

问题描述：将 $n$ 个写有 $1 \sim n$ 的球放入标号为 $1 \sim n$ 的盒子中，使得每个球的标号与其所在的盒子标号都不相同，求方案数 $D_n$。 * 递推关系：假设前 $n-1$ 个球已完成错排。当加入第 $n$ 个球时： 1. 如果它与前面某球 $i$（有 $n-1$ 种选择）交换位置，且其余 $n-2$ 个球构成错排，此时有 $(n-1) \cdot D_{n-2}$ 种情况。 2. 如果它与前面某球 $i$ 交换，但其余 $n-1$ 个球已经构成错排，此时有 $(n-1) \cdot D_{n-1}$ 种情况。 * 公式： $$D_1 = 0, \quad D_2 = 1$$ $$D_n = (n-1)(D_{n-1} + D_{n-2}) \quad (n \ge 3)$$

3.3 卡特兰数（Catalan Numbers）

应用场景： 1. 长度为 $2n$ 的合法括号序列数量。 2. $n$ 个节点的二叉树不同形态数量。 3. 出栈序列数（$n$ 个数依次入栈，求可能的出栈序列数）。 4. 在网格图上，从 $(0,0)$ 走到 $(n,n)$ 且不穿过对角线 $y = x$ 的路径数。

常用计算公式： $$H_n = \frac{C_{2n}^n}{n+1} = C_{2n}^n - C_{2n}^{n-1}$$
递推式： $$H_0 = 1, \quad H_n = \sum_{i=0}^{n-1} H_i H_{n-1-i}$$

附录：数列的基础性质与信奥扩展

在处理排列组合和动态规划时，常常会伴随着等差数列与等比数列的求和。

1. 等差数列（Arithmetic Progression）

通项公式：$a_n = a_1 + (n-1)d$
求和公式：$S_n = \frac{a_1 + a_n}{2} \cdot n = n a_1 + \frac{n(n-1)}{2}d$

2. 等比数列（Geometric Progression）

通项公式：$a_n = a_1 q^{n-1}$
求和公式（当 $q \neq 1$ 时）：$S_n = a_1 \frac{1-q^n}{1-q}$

信奥考点：等比数列模意义下求和 当需要在模 $P$ 意义下求等比数列和 $S_n$ 时，若 $1-q$ 与 $P$ 互质，可直接用逆元计算： $$S_n \equiv a_1 \cdot (1-q^n) \cdot (1-q)^{-1} \pmod P$$ 若 $1-q$ 与 $P$ 不互质（或者 $P$ 不是质数），可以使用分治法（Divide and Conquer）在 $O(\log n)$ 内计算： $$S_n = \begin{cases} a_1 & n=1 \ (1 + q^{n/2}) S_{n/2} & n \text{ 为偶数} \ (1 + q^{(n-1)/2}) S_{(n-1)/2} + a_1 q^{n-1} & n \text{ 为奇数} \end{cases}$$

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

组合与组合数学基础讲义