这份讲义将针对您提供的大纲进行系统性的梳理。由于内容跨度较广，本讲义将重点放在**数学原理的严谨推导、性质分析、C++11 标准下的高效算法实现**，并在最后提供习题与详细解析。

---

# C++11 与算法数学基础讲义

---

## 第一部分：初等数学

### 1. 代数（高中部分）与几何基础
#### 1.1 一元二次方程与数列
一元二次方程 $ax^2 + bx + c = 0 \ (a \neq 0)$ 的求根公式为：
$$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$
利用 C++11 的 `std::complex`，我们可以统一处理实根与虚根。

#### 1.2 点到直线的距离
设点 $P(x\_0, y\_0)$，直线方程为 $Ax + By + C = 0$，则距离 $d$ 为：
$$d = \frac{|Ax\_0 + By\_0 + C|}{\sqrt{A^2 + B^2}}$$

#### 1.3 C++11 代码实现
```cpp
#include <iostream>
#include <cmath>
#include <complex>
#include <utility>

// 求解一元二次方程
std::pair<std::complex<double>, std::complex<double>> solve_quadratic(double a, double b, double c) {
    std::complex<double> discriminant = b * b - 4 * a * c;
    std::complex<double> r1 = (-b + std::sqrt(discriminant)) / (2.0 * a);
    std::complex<double> r2 = (-b - std::sqrt(discriminant)) / (2.0 * a);
    return {r1, r2};
}

// 计算点到直线的距离
double point_to_line_dist(double x0, double y0, double A, double B, double C) {
    return std::abs(A * x0 + B * y0 + C) / std::hypot(A, B);
}
```

---

## 第二部分：初等数论

### 1. 同余式与裴蜀定理
#### 1.1 同余定义与基本性质
若 $m \mid (a - b)$（$m$ 整除 $a-b$），则称 $a$ 与 $b$ 模 $m$ 同余，记作 $a \equiv b \pmod m$。
*   **自反性**：$a \equiv a \pmod m$
*   **对称性**：若 $a \equiv b \pmod m$，则 $b \equiv a \pmod m$
*   **传递性**：若 $a \equiv b \pmod m$ 且 $b \equiv c \pmod m$，则 $a \equiv c \pmod m$
*   **可加/乘性**：若 $a \equiv b \pmod m$ 且 $c \equiv d \pmod m$，则 $a \pm c \equiv b \pm d \pmod m$，且 $ac \equiv bd \pmod m$。

#### 1.2 裴蜀定理 (Bézout's Identity)
**定理**：对任意整数 $a, b$，关于未知数 $x, y$ 的线性丢番图方程：
$$ax + by = c$$
有整数解当且仅当 $\gcd(a, b) \mid c$。特别地，必然存在整数 $x, y$ 使得 $ax + by = \gcd(a, b)$。

---

### 2. 扩展欧几里得算法 (ExGCD)
#### 2.1 递归公式推导
我们希望求解 $ax + by = \gcd(a, b)$。
根据欧几里得算法，$\gcd(a, b) = \gcd(b, a \bmod b)$。
设我们已求出下一层递归的解 $x', y'$，满足：
$$b x' + (a \bmod b) y' = \gcd(b, a \bmod b) = \gcd(a, b)$$
因为 $a \bmod b = a - \lfloor \frac{a}{b} \rfloor b$，代入上式：
$$b x' + \left(a - \lfloor \frac{a}{b} \rfloor b\right) y' = a y' + b \left(x' - \lfloor \frac{a}{b} \rfloor y'\right) = \gcd(a, b)$$
对比原式 $ax + by = \gcd(a, b)$ 的系数，可得递推关系：
$$\begin{cases} x = y' \\ y = x' - \lfloor \frac{a}{b} \rfloor y' \end{cases}$$

#### 2.2 C++11 实现
```cpp
#include <tuple>

// 返回 {gcd, x, y} 满足 a*x + b*y = gcd
std::tuple<long long, long long, long long> ext_gcd(long long a, long long b) {
    if (b == 0) {
        return std::make_tuple(a, 1LL, 0LL);
    }
    long long g, x_next, y_next;
    std::tie(g, x_next, y_next) = ext_gcd(b, a % b);
    return std::make_tuple(g, y_next, x_next - (a / b) * y_next);
}
```

---

### 3. 欧拉函数与欧拉定理
#### 3.1 欧拉函数 $\varphi(n)$ 的定义与公式
$\varphi(n)$ 表示 $[1, n]$ 中与 $n$ 互质的整数个数。
对于 $n = p\_1^{a\_1} p\_2^{a\_2} \dots p\_k^{a\_k}$（素因子分解）：
$$\varphi(n) = n \prod\_{i=1}^k \left(1 - \frac{1}{p\_i}\right)$$

##### **公式推导（容斥原理）**
从 $1$ 到 $n$ 的数中，是 $p\_i$ 的倍数的数有 $\frac{n}{p\_i}$ 个。我们要去掉这些倍数。
根据容斥原理：
$$\varphi(n) = n - \sum \frac{n}{p\_i} + \sum \frac{n}{p\_i p\_j} - \dots = n \prod\_{i=1}^k \left(1 - \frac{1}{p\_i}\right)$$

#### 3.2 欧拉定理与费马小定理
*   **欧拉定理**：若 $\gcd(a, m) = 1$，则：
    $$a^{\varphi(m)} \equiv 1 \pmod m$$
*   **费马小定理**：若 $p$ 为质数，且 $\gcd(a, p) = 1$，则 $\varphi(p) = p-1$，代入欧拉定理得：
    $$a^{p-1} \equiv 1 \pmod p$$

#### 3.3 威尔逊定理 (Wilson's Theorem)
**定理**：在正整数中，$p$ 是质数的充要条件是：
$$(p-1)! \equiv -1 \pmod p$$
*简要证明*：若 $p$ 是质数，则在 $\pmod p$ 意义下，除了 $1$ 和 $p-1$ 的逆元是其自身外，其余 $[2, p-2]$ 中的数均可两两配对，使得两数乘积模 $p$ 余 $1$。因此乘积为 $1 \cdot (p-1) \cdot 1 \equiv -1 \pmod p$。

#### 3.4 C++11 实现：线性筛求欧拉函数
```cpp
#include <vector>

std::vector<int> get_phi_to_n(int n) {
    std::vector<int> phi(n + 1);
    std::vector<int> primes;
    std::vector<bool> is_prime(n + 1, true);
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (int p : primes) {
            if (i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p; // p 是 i 的因子，根据公式，新引入的质因子p不改变(1 - 1/p)项，直接乘p
                break;
            } else {
                phi[i * p] = phi[i] * (p - 1); // p 与 i 互质，积性性质 phi(i*p) = phi(i)*phi(p)
            }
        }
    }
    return phi;
}
```

---

### 4. 模运算意义下的逆元
若 $a \cdot x \equiv 1 \pmod m$，称 $x$ 为 $a$ 模 $m$ 的逆元，记作 $a^{-1}$。

#### 4.1 三种求解方法
1.  **费马小定理法**（要求 $m$ 是质数）：$a^{-1} \equiv a^{m-2} \pmod m$。
2.  **扩展欧几里得法**（要求 $\gcd(a, m) = 1$）：求解 $ax + my = 1$，求得的 $x$ 即为逆元。
3.  **线性递推求逆元**（求 $1 \dots n$ 的所有逆元，要求 $p$ 为质数）：
    设 $p = k \cdot i + r$（其中 $k = \lfloor p/i \rfloor, r = p \bmod i$）。
    在模 $p$ 下：
    $$k \cdot i + r \equiv 0 \pmod p \implies r \equiv -k \cdot i \pmod p$$
    同乘 $i^{-1} \cdot r^{-1}$：
    $$i^{-1} \equiv -k \cdot r^{-1} \pmod p \implies i^{-1} \equiv -\lfloor p/i \rfloor \cdot (p \bmod i)^{-1} \pmod p$$

#### 4.2 C++11 实现（线性递推）
```cpp
#include <vector>

std::vector<long long> get_inv_to_n(int n, long long p) {
    std::vector<long long> inv(n + 1);
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = (p - p / i) * inv[p % i] % p;
    }
    return inv;
}
```

---

### 5. 中国剩余定理 (Chinese Remainder Theorem, CRT)
#### 5.1 构造方法
设 $m\_1, m\_2, \dots, m\_k$ 两两互质，对于同余方程组：
$$\begin{cases} 
x \equiv a\_1 \pmod {m\_1} \\
x \equiv a\_2 \pmod {m\_2} \\
\vdots \\
x \equiv a\_k \pmod {m\_k} 
\end{cases}$$
设 $M = \prod\_{i=1}^k m\_i$，$M\_i = M / m\_i$。由于 $\gcd(M\_i, m\_i) = 1$，存在逆元 $t\_i$ 使得 $M\_i t\_i \equiv 1 \pmod {m\_i}$。
方程组的唯一通解（模 $M$）为：
$$x = \sum\_{i=1}^k a\_i M\_i t\_i \pmod M$$

#### 5.2 C++11 实现
```cpp
#include <vector>
#include <numeric>

// 辅助函数：快速幂求逆元（假设 m 为质数，若不是请用 ex_gcd）
long long qpow(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

long long get_inverse_exgcd(long long a, long long m) {
    long long g, x, y;
    std::tie(g, x, y) = ext_gcd(a, m);
    return (x % m + m) % m;
}

long long chinese_remainder_theorem(const std::vector<long long>& a, const std::vector<long long>& m) {
    long long M = 1;
    for (auto val : m) M *= val;
    long long x = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        long long Mi = M / m[i];
        long long ti = get_inverse_exgcd(Mi, m[i]);
        x = (x + a[i] * Mi % M * ti % M) % M;
    }
    return (x + M) % M;
}
```

---

## 第三部分：离散与组合数学

### 1. 多重集排列与组合
#### 1.1 多重集排列
设多重集 $S = \{n\_1 \cdot a\_1, n\_2 \cdot a\_2, \dots, n\_k \cdot a\_k\}$，其元素总数 $n = \sum n\_i$。其全排列数为：
$$\frac{n!}{n\_1! n\_2! \dots n\_k!}$$

#### 1.2 多重集组合（放球问题 / 隔板法）
从包含 $n$ 种不同元素的无穷多重集中，选择 $r$ 个元素的组合数（即允许重复选择），等价于将 $r$ 个无区别的球放入 $n$ 个有区别的盒子（盒子可空），其方案数为：
$$\binom{n + r - 1}{r}$$

---

### 2. 特殊排列与原理
#### 2.1 错排列 (Derangement)
每一个元素都不在自己原本位置上的排列。
递推公式：$D\_n = (n-1)(D\_{n-1} + D\_{n-2})$，初始值 $D\_1 = 0, D\_2 = 1$。
*证明思路*：第 $n$ 个元素可以放在前 $n-1$ 个位置之一（设放在位置 $i$，有 $n-1$ 种选法）。此时：
*   若元素 $i$ 恰好放在了位置 $n$，剩下的 $n-2$ 个元素做错排，方案数为 $D\_{n-2}$；
*   若元素 $i$ 不放在位置 $n$，则等价于将包括元素 $i$ 在内的 $n-1$ 个元素做错排，方案数为 $D\_{n-1}$。

#### 2.2 圆排列 (Circular Permutation)
$n$ 个不同元素围成一个圈的排列数：
$$Q\_n = \frac{P\_n^n}{n} = (n-1)!$$

#### 2.3 容斥原理 (Inclusion-Exclusion Principle)
$$\left| \bigcup\_{i=1}^n A\_i \right| = \sum\_{i=1}^n |A\_i| - \sum\_{1 \le i < j \le n} |A\_i \cap A\_j| + \dots + (-1)^{n-1} |A\_1 \cap \dots \cap A\_n|$$

---

### 3. 卡特兰数 (Catalan Number)
#### 3.1 递推与通项
前几项为：$1, 1, 2, 5, 14, 42, 132, \dots$
*   **通项公式**：$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)$

#### 3.2 C++11 实现
```cpp
// 结合逆元计算卡特兰数 H_n (模质数 mod)
long long catalan_num(int n, long long mod) {
    if (n == 0 || n == 1) return 1;
    long long num = 1, den = 1;
    for (int i = 1; i <= n; ++i) {
        num = (num * (n + i)) % mod;
        den = (den * i) % mod;
    }
    den = (den * (n + 1)) % mod;
    return num * qpow(den, mod - 2, mod) % mod;
}
```

---

## 第四部分：线性代数

### 1. 向量与矩阵运算
在 C++11 中，我们可以使用嵌套的 `std::vector` 和 `using` 模板别名来优雅地定义矩阵和向量。

```cpp
#include <vector>
#include <stdexcept>

using Vector = std::vector<double>;
using Matrix = std::vector<Vector>;

// 矩阵乘法
Matrix multiply(const Matrix& A, const Matrix& B) {
    int r1 = A.size(), c1 = A[0].size();
    int r2 = B.size(), c2 = B[0].size();
    if (c1 != r2) throw std::invalid_argument("Dimension mismatch");
    
    Matrix C(r1, Vector(c2, 0.0));
    for (int i = 0; i < r1; ++i) {
        for (int k = 0; k < c1; ++k) {
            if (A[i][k] == 0.0) continue; // 稀疏优化
            for (int j = 0; j < c2; ++j) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}
```

---

### 2. 稀疏矩阵的概念与压缩存储 (CSR 格式)
在处理大规模数据时，传统二维数组存储稀疏矩阵会造成空间浪费。**CSR (Compressed Sparse Row)** 是一种经典的压缩存储方案，使用三个一维数组表示：
*   `values`：非零元素的值。
*   `col_indices`：每个非零元素对应的列索引。
*   `row_offsets`：存储每一行在 `values` 中的起始位置，大小为 $Row+1$。

```cpp
struct CSRMatrix {
    std::vector<double> values;
    std::vector<int> col_indices;
    std::vector<int> row_offsets;
    int rows, cols;
};
```

---

### 3. 高斯消元法 (Gaussian Elimination)
用于求解线性方程组 $Ax = B$。主要步骤包括：
1.  **消元过程**：通过初等行变换将增广矩阵 $[A | B]$ 转换为上三角矩阵。
2.  **回代过程**：从最后一行开始，逐步求出未知数 $x\_i$ 的值。

#### 3.1 C++11 实现（含部分主元选择，避免浮点误差）
```cpp
#include <cmath>

constexpr double EPS = 1e-9;

// 返回解向量，若无唯一解返回空向量
Vector gaussian_elimination(Matrix A, Vector b) {
    int n = A.size();
    // 构造增广矩阵
    for (int i = 0; i < n; ++i) {
        A[i].push_back(b[i]);
    }

for (int i = 0; i < n; ++i) {
        // 寻找主元
        int pivot = i;
        for (int j = i + 1; j < n; ++j) {
            if (std::abs(A[j][i]) > std::abs(A[pivot][i])) {
                pivot = j;
            }
        }
        if (std::abs(A[pivot][i]) < EPS) {
            return {}; // 无唯一解（奇异矩阵）
        }
        std::swap(A[i], A[pivot]);

// 行消元
        for (int j = i + 1; j < n; ++j) {
            double factor = A[j][i] / A[i][i];
            for (int k = i; k <= n; ++k) {
                A[j][k] -= factor * A[i][k];
            }
        }
    }

// 回代
    Vector x(n);
    for (int i = n - 1; i >= 0; --i) {
        double sum = 0.0;
        for (int j = i + 1; j < n; ++j) {
            sum += A[i][j] * x[j];
        }
        x[i] = (A[i][n] - sum) / A[i][i];
    }
    return x;
}
```

---

## 第五部分：练习题与解析

### 练习题 1：同余方程与扩展欧几里得
**题目**：求解模线性同余方程 $14x \equiv 6 \pmod{20}$。请给出通解的数学表达式，并用程序求出 $[0, 19]$ 范围内的所有解。

### 练习题 2：错排与容斥原理
**题目**：将 5 封不同的信放入 5 个不同的信封中，求：
1. 恰好有 2 封信放对位置的方案数。
2. 5 封信全部放错的方案数（即全错排）。

### 练习题 3：高斯消元应用
**题目**：使用高斯消元法求解如下方程组：
$$\begin{cases}
2x + y - z = 8 \\
-3x - y + 2z = -11 \\
-2x + y + 2z = -3
\end{cases}$$

---

### 详细解析与答案

#### 习题 1 解析：
1.  **数学推导**：
    原方程等价于 $14x - 20y = 6$。
    令 $a = 14, b = 20, c = 6$。首先求 $g = \gcd(14, 20) = 2$。
    由于 $2 \mid 6$，方程有解。
    除以 $g$，简化为：$7x - 10y = 3 \implies 7x \equiv 3 \pmod{10}$。
    利用扩展欧几里得求 $7x' + 10y' = 1$ 的解：
    经计算，$7 \times 3 - 10 \times 2 = 1$，所以特解 $x' = 3$。
    乘以系数 $3$（由于 $3/1 = 3$）：$x\_0 = 3 \times 3 = 9$。
    在模 $20$ 意义下，所有解的步长为 $\frac{20}{\gcd(14, 20)} = 10$。
    所以两个解为：$x\_1 = 9$，$x\_2 = 19$。

2.  **C++11 验证程序**：
    ```cpp
    #include <iostream>
    int main() {
        // 直接验证
        for (int x = 0; x < 20; ++x) {
            if ((14 * x) % 20 == 6) {
                std::cout << "x = " << x << std::endl; // 输出 9 和 19
            }
        }
        return 0;
    }
    ```

#### 习题 2 解析：
1.  **恰好有 2 封信放对位置**：
    *   第一步：选择哪 2 封信放对，方案数为 $\binom{5}{2} = 10$。
    *   第二步：剩下的 3 封信必须全部放错，即对 3 个元素做全错排。
        $D\_3 = (3-1)(D\_2 + D\_1) = 2 \times (1 + 0) = 2$。
    *   根据乘法原理，总方案数为 $\binom{5}{2} \times D\_3 = 10 \times 2 = 20$。
2.  **5 封信全部放错**：
    *   即 $D\_5 = 4 \times (D\_4 + D\_3)$。
    *   先求 $D\_4 = 3 \times (D\_3 + D\_2) = 3 \times (2 + 1) = 9$。
    *   所以 $D\_5 = 4 \times (9 + 2) = 44$。

#### 习题 3 解析：
1.  **增广矩阵表示**：
    $$\left[ \begin{array}{ccc|c} 
    2 & 1 & -1 & 8 \\ 
    -3 & -1 & 2 & -11 \\ 
    -2 & 1 & 2 & -3 
    \end{array} \right]$$
2.  **消元过程**：
    *   第2行加上第1行的 1.5 倍：
        $$R\_2 \leftarrow R\_2 + 1.5 R\_1 \implies \left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 0.5 & 0.5 & 1 \\ -2 & 1 & 2 & -3 \end{array} \right]$$
    *   第3行加上第1行：
        $$R\_3 \leftarrow R\_3 + R\_1 \implies \left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 0.5 & 0.5 & 1 \\ 0 & 2 & 1 & 5 \end{array} \right]$$
    *   交换 $R\_2$ 和 $R\_3$（为了数值稳定性，选取更大的主元）：
        $$\left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 2 & 1 & 5 \\ 0 & 0.5 & 0.5 & 1 \end{array} \right]$$
    *   第3行减去第2行的 0.25 倍：
        $$R\_3 \leftarrow R\_3 - 0.25 R\_2 \implies \left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \\ 0 & 2 & 1 & 5 \\ 0 & 0 & 0.25 & -0.25 \end{array} \right]$$
3.  **回代求解**：
    *   $0.25 z = -0.25 \implies z = -1$
    *   $2y + z = 5 \implies 2y - 1 = 5 \implies y = 3$
    *   $2x + y - z = 8 \implies 2x + 3 - (-1) = 8 \implies 2x + 4 = 8 \implies x = 2$
    
    **最终解**为：$x = 2, y = 3, z = -1$。可以使用前文提供的 `gaussian_elimination` 代码进行无缝验证。

这份讲义将针对您提供的大纲进行系统性的梳理。由于内容跨度较广，本讲义将重点放在数学原理的严谨推导、性质分析、C++11 标准下的高效算法实现，并在最后提供习题与详细解析。

C++11 与算法数学基础讲义

第一部分：初等数学

1. 代数（高中部分）与几何基础

1.1 一元二次方程与数列

一元二次方程 $ax^2 + bx + c = 0 \ (a \neq 0)$ 的求根公式为： $$x = \frac{-b \pm \sqrt{b^2 - 4ac}}{2a}$$ 利用 C++11 的 std::complex，我们可以统一处理实根与虚根。

1.2 点到直线的距离

设点 $P(x_0, y_0)$，直线方程为 $Ax + By + C = 0$，则距离 $d$ 为： $$d = \frac{|Ax_0 + By_0 + C|}{\sqrt{A^2 + B^2}}$$

1.3 C++11 代码实现

#include <iostream>
#include <cmath>
#include <complex>
#include <utility>

// 求解一元二次方程
std::pair<std::complex<double>, std::complex<double>> solve_quadratic(double a, double b, double c) {
    std::complex<double> discriminant = b * b - 4 * a * c;
    std::complex<double> r1 = (-b + std::sqrt(discriminant)) / (2.0 * a);
    std::complex<double> r2 = (-b - std::sqrt(discriminant)) / (2.0 * a);
    return {r1, r2};
}

// 计算点到直线的距离
double point_to_line_dist(double x0, double y0, double A, double B, double C) {
    return std::abs(A * x0 + B * y0 + C) / std::hypot(A, B);
}

第二部分：初等数论

1. 同余式与裴蜀定理

1.1 同余定义与基本性质

若 $m \mid (a - b)$（$m$ 整除 $a-b$），则称 $a$ 与 $b$ 模 $m$ 同余，记作 $a \equiv b \pmod m$。 * 自反性：$a \equiv a \pmod m$ * 对称性：若 $a \equiv b \pmod m$，则 $b \equiv a \pmod m$ * 传递性：若 $a \equiv b \pmod m$ 且 $b \equiv c \pmod m$，则 $a \equiv c \pmod m$ * 可加/乘性：若 $a \equiv b \pmod m$ 且 $c \equiv d \pmod m$，则 $a \pm c \equiv b \pm d \pmod m$，且 $ac \equiv bd \pmod m$。

1.2 裴蜀定理 (Bézout's Identity)

定理：对任意整数 $a, b$，关于未知数 $x, y$ 的线性丢番图方程： $$ax + by = c$$ 有整数解当且仅当 $\gcd(a, b) \mid c$。特别地，必然存在整数 $x, y$ 使得 $ax + by = \gcd(a, b)$。

2. 扩展欧几里得算法 (ExGCD)

2.1 递归公式推导

我们希望求解 $ax + by = \gcd(a, b)$。根据欧几里得算法，$\gcd(a, b) = \gcd(b, a \bmod b)$。设我们已求出下一层递归的解 $x', y'$，满足： $$b x' + (a \bmod b) y' = \gcd(b, a \bmod b) = \gcd(a, b)$$ 因为 $a \bmod b = a - \lfloor \frac{a}{b} \rfloor b$，代入上式： $$b x' + \left(a - \lfloor \frac{a}{b} \rfloor b\right) y' = a y' + b \left(x' - \lfloor \frac{a}{b} \rfloor y'\right) = \gcd(a, b)$$ 对比原式 $ax + by = \gcd(a, b)$ 的系数，可得递推关系： $$\begin{cases} x = y' \ y = x' - \lfloor \frac{a}{b} \rfloor y' \end{cases}$$

2.2 C++11 实现

#include <tuple>

// 返回 {gcd, x, y} 满足 a*x + b*y = gcd
std::tuple<long long, long long, long long> ext_gcd(long long a, long long b) {
    if (b == 0) {
        return std::make_tuple(a, 1LL, 0LL);
    }
    long long g, x_next, y_next;
    std::tie(g, x_next, y_next) = ext_gcd(b, a % b);
    return std::make_tuple(g, y_next, x_next - (a / b) * y_next);
}

3. 欧拉函数与欧拉定理

3.1 欧拉函数 $\varphi(n)$ 的定义与公式

$\varphi(n)$ 表示 $[1, n]$ 中与 $n$ 互质的整数个数。对于 $n = p_1^{a_1} p_2^{a_2} \dots p_k^{a_k}$（素因子分解）： $$\varphi(n) = n \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)$$

公式推导（容斥原理）

从 $1$ 到 $n$ 的数中，是 $p_i$ 的倍数的数有 $\frac{n}{p_i}$ 个。我们要去掉这些倍数。根据容斥原理： $$\varphi(n) = n - \sum \frac{n}{p_i} + \sum \frac{n}{p_i p_j} - \dots = n \prod_{i=1}^k \left(1 - \frac{1}{p_i}\right)$$

3.2 欧拉定理与费马小定理

欧拉定理：若 $\gcd(a, m) = 1$，则： $$a^{\varphi(m)} \equiv 1 \pmod m$$
费马小定理：若 $p$ 为质数，且 $\gcd(a, p) = 1$，则 $\varphi(p) = p-1$，代入欧拉定理得： $$a^{p-1} \equiv 1 \pmod p$$

3.3 威尔逊定理 (Wilson's Theorem)

定理：在正整数中，$p$ 是质数的充要条件是： $$(p-1)! \equiv -1 \pmod p$$ 简要证明：若 $p$ 是质数，则在 $\pmod p$ 意义下，除了 $1$ 和 $p-1$ 的逆元是其自身外，其余 $[2, p-2]$ 中的数均可两两配对，使得两数乘积模 $p$ 余 $1$。因此乘积为 $1 \cdot (p-1) \cdot 1 \equiv -1 \pmod p$。

3.4 C++11 实现：线性筛求欧拉函数

#include <vector>

std::vector<int> get_phi_to_n(int n) {
    std::vector<int> phi(n + 1);
    std::vector<int> primes;
    std::vector<bool> is_prime(n + 1, true);
    phi[1] = 1;
    for (int i = 2; i <= n; ++i) {
        if (is_prime[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (int p : primes) {
            if (i * p > n) break;
            is_prime[i * p] = false;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p; // p 是 i 的因子，根据公式，新引入的质因子p不改变(1 - 1/p)项，直接乘p
                break;
            } else {
                phi[i * p] = phi[i] * (p - 1); // p 与 i 互质，积性性质 phi(i*p) = phi(i)*phi(p)
            }
        }
    }
    return phi;
}

4. 模运算意义下的逆元

若 $a \cdot x \equiv 1 \pmod m$，称 $x$ 为 $a$ 模 $m$ 的逆元，记作 $a^{-1}$。

4.1 三种求解方法

费马小定理法（要求 $m$ 是质数）：$a^{-1} \equiv a^{m-2} \pmod m$。
扩展欧几里得法（要求 $\gcd(a, m) = 1$）：求解 $ax + my = 1$，求得的 $x$ 即为逆元。
线性递推求逆元（求 $1 \dots n$ 的所有逆元，要求 $p$ 为质数）：设 $p = k \cdot i + r$（其中 $k = \lfloor p/i \rfloor, r = p \bmod i$）。在模 $p$ 下： $$k \cdot i + r \equiv 0 \pmod p \implies r \equiv -k \cdot i \pmod p$$ 同乘 $i^{-1} \cdot r^{-1}$： $$i^{-1} \equiv -k \cdot r^{-1} \pmod p \implies i^{-1} \equiv -\lfloor p/i \rfloor \cdot (p \bmod i)^{-1} \pmod p$$

4.2 C++11 实现（线性递推）

#include <vector>

std::vector<long long> get_inv_to_n(int n, long long p) {
    std::vector<long long> inv(n + 1);
    inv[1] = 1;
    for (int i = 2; i <= n; ++i) {
        inv[i] = (p - p / i) * inv[p % i] % p;
    }
    return inv;
}

5. 中国剩余定理 (Chinese Remainder Theorem, CRT)

5.1 构造方法

设 $m_1, m_2, \dots, m_k$ 两两互质，对于同余方程组： $$\begin{cases} x \equiv a_1 \pmod {m_1} \ x \equiv a_2 \pmod {m_2} \ \vdots \ x \equiv a_k \pmod {m_k} \end{cases}$$ 设 $M = \prod_{i=1}^k m_i$，$M_i = M / m_i$。由于 $\gcd(M_i, m_i) = 1$，存在逆元 $t_i$ 使得 $M_i t_i \equiv 1 \pmod {m_i}$。方程组的唯一通解（模 $M$）为： $$x = \sum_{i=1}^k a_i M_i t_i \pmod M$$

5.2 C++11 实现

#include <vector>
#include <numeric>

// 辅助函数：快速幂求逆元（假设 m 为质数，若不是请用 ex_gcd）
long long qpow(long long base, long long exp, long long mod) {
    long long res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % mod;
        base = (base * base) % mod;
        exp >>= 1;
    }
    return res;
}

long long get_inverse_exgcd(long long a, long long m) {
    long long g, x, y;
    std::tie(g, x, y) = ext_gcd(a, m);
    return (x % m + m) % m;
}

long long chinese_remainder_theorem(const std::vector<long long>& a, const std::vector<long long>& m) {
    long long M = 1;
    for (auto val : m) M *= val;
    long long x = 0;
    for (size_t i = 0; i < a.size(); ++i) {
        long long Mi = M / m[i];
        long long ti = get_inverse_exgcd(Mi, m[i]);
        x = (x + a[i] * Mi % M * ti % M) % M;
    }
    return (x + M) % M;
}

第三部分：离散与组合数学

1. 多重集排列与组合

1.1 多重集排列

设多重集 $S = {n_1 \cdot a_1, n_2 \cdot a_2, \dots, n_k \cdot a_k}$，其元素总数 $n = \sum n_i$。其全排列数为： $$\frac{n!}{n_1! n_2! \dots n_k!}$$

1.2 多重集组合（放球问题 / 隔板法）

从包含 $n$ 种不同元素的无穷多重集中，选择 $r$ 个元素的组合数（即允许重复选择），等价于将 $r$ 个无区别的球放入 $n$ 个有区别的盒子（盒子可空），其方案数为： $$\binom{n + r - 1}{r}$$

2. 特殊排列与原理

2.1 错排列 (Derangement)

每一个元素都不在自己原本位置上的排列。递推公式：$D_n = (n-1)(D_{n-1} + D_{n-2})$，初始值 $D_1 = 0, D_2 = 1$。 证明思路：第 $n$ 个元素可以放在前 $n-1$ 个位置之一（设放在位置 $i$，有 $n-1$ 种选法）。此时： * 若元素 $i$ 恰好放在了位置 $n$，剩下的 $n-2$ 个元素做错排，方案数为 $D_{n-2}$； * 若元素 $i$ 不放在位置 $n$，则等价于将包括元素 $i$ 在内的 $n-1$ 个元素做错排，方案数为 $D_{n-1}$。

2.2 圆排列 (Circular Permutation)

$n$ 个不同元素围成一个圈的排列数： $$Q_n = \frac{P_n^n}{n} = (n-1)!$$

2.3 容斥原理 (Inclusion-Exclusion Principle)

$$\left| \bigcup_{i=1}^n A_i \right| = \sum_{i=1}^n |A_i| - \sum_{1 \le i < j \le n} |A_i \cap A_j| + \dots + (-1)^{n-1} |A_1 \cap \dots \cap A_n|$$

3. 卡特兰数 (Catalan Number)

3.1 递推与通项

前几项为：$1, 1, 2, 5, 14, 42, 132, \dots$ * 通项公式：$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)$

3.2 C++11 实现

// 结合逆元计算卡特兰数 H_n (模质数 mod)
long long catalan_num(int n, long long mod) {
    if (n == 0 || n == 1) return 1;
    long long num = 1, den = 1;
    for (int i = 1; i <= n; ++i) {
        num = (num * (n + i)) % mod;
        den = (den * i) % mod;
    }
    den = (den * (n + 1)) % mod;
    return num * qpow(den, mod - 2, mod) % mod;
}

第四部分：线性代数

1. 向量与矩阵运算

在 C++11 中，我们可以使用嵌套的 std::vector 和 using 模板别名来优雅地定义矩阵和向量。

#include <vector>
#include <stdexcept>

using Vector = std::vector<double>;
using Matrix = std::vector<Vector>;

// 矩阵乘法
Matrix multiply(const Matrix& A, const Matrix& B) {
    int r1 = A.size(), c1 = A[0].size();
    int r2 = B.size(), c2 = B[0].size();
    if (c1 != r2) throw std::invalid_argument("Dimension mismatch");

    Matrix C(r1, Vector(c2, 0.0));
    for (int i = 0; i < r1; ++i) {
        for (int k = 0; k < c1; ++k) {
            if (A[i][k] == 0.0) continue; // 稀疏优化
            for (int j = 0; j < c2; ++j) {
                C[i][j] += A[i][k] * B[k][j];
            }
        }
    }
    return C;
}

2. 稀疏矩阵的概念与压缩存储 (CSR 格式)

在处理大规模数据时，传统二维数组存储稀疏矩阵会造成空间浪费。CSR (Compressed Sparse Row) 是一种经典的压缩存储方案，使用三个一维数组表示： * values：非零元素的值。 * col_indices：每个非零元素对应的列索引。 * row_offsets：存储每一行在 values 中的起始位置，大小为 $Row+1$。

struct CSRMatrix {
    std::vector<double> values;
    std::vector<int> col_indices;
    std::vector<int> row_offsets;
    int rows, cols;
};

3. 高斯消元法 (Gaussian Elimination)

用于求解线性方程组 $Ax = B$。主要步骤包括： 1. 消元过程：通过初等行变换将增广矩阵 $[A | B]$ 转换为上三角矩阵。 2. 回代过程：从最后一行开始，逐步求出未知数 $x_i$ 的值。

3.1 C++11 实现（含部分主元选择，避免浮点误差）

#include <cmath>

constexpr double EPS = 1e-9;

// 返回解向量，若无唯一解返回空向量
Vector gaussian_elimination(Matrix A, Vector b) {
    int n = A.size();
    // 构造增广矩阵
    for (int i = 0; i < n; ++i) {
        A[i].push_back(b[i]);
    }

    for (int i = 0; i < n; ++i) {
        // 寻找主元
        int pivot = i;
        for (int j = i + 1; j < n; ++j) {
            if (std::abs(A[j][i]) > std::abs(A[pivot][i])) {
                pivot = j;
            }
        }
        if (std::abs(A[pivot][i]) < EPS) {
            return {}; // 无唯一解（奇异矩阵）
        }
        std::swap(A[i], A[pivot]);

        // 行消元
        for (int j = i + 1; j < n; ++j) {
            double factor = A[j][i] / A[i][i];
            for (int k = i; k <= n; ++k) {
                A[j][k] -= factor * A[i][k];
            }
        }
    }

    // 回代
    Vector x(n);
    for (int i = n - 1; i >= 0; --i) {
        double sum = 0.0;
        for (int j = i + 1; j < n; ++j) {
            sum += A[i][j] * x[j];
        }
        x[i] = (A[i][n] - sum) / A[i][i];
    }
    return x;
}

第五部分：练习题与解析

练习题 1：同余方程与扩展欧几里得

题目：求解模线性同余方程 $14x \equiv 6 \pmod{20}$。请给出通解的数学表达式，并用程序求出 $[0, 19]$ 范围内的所有解。

练习题 2：错排与容斥原理

题目：将 5 封不同的信放入 5 个不同的信封中，求： 1. 恰好有 2 封信放对位置的方案数。 2. 5 封信全部放错的方案数（即全错排）。

练习题 3：高斯消元应用

题目：使用高斯消元法求解如下方程组： $$\begin{cases} 2x + y - z = 8 \ -3x - y + 2z = -11 \ -2x + y + 2z = -3 \end{cases}$$

详细解析与答案

习题 1 解析：

数学推导：原方程等价于 $14x - 20y = 6$。令 $a = 14, b = 20, c = 6$。首先求 $g = \gcd(14, 20) = 2$。由于 $2 \mid 6$，方程有解。除以 $g$，简化为：$7x - 10y = 3 \implies 7x \equiv 3 \pmod{10}$。利用扩展欧几里得求 $7x' + 10y' = 1$ 的解：经计算，$7 \times 3 - 10 \times 2 = 1$，所以特解 $x' = 3$。乘以系数 $3$（由于 $3/1 = 3$）：$x_0 = 3 \times 3 = 9$。在模 $20$ 意义下，所有解的步长为 $\frac{20}{\gcd(14, 20)} = 10$。所以两个解为：$x_1 = 9$，$x_2 = 19$。
C++11 验证程序： cpp #include <iostream> int main() { // 直接验证 for (int x = 0; x < 20; ++x) { if ((14 * x) % 20 == 6) { std::cout << "x = " << x << std::endl; // 输出 9 和 19 } } return 0; }

习题 2 解析：

恰好有 2 封信放对位置：
- 第一步：选择哪 2 封信放对，方案数为 $\binom{5}{2} = 10$。
- 第二步：剩下的 3 封信必须全部放错，即对 3 个元素做全错排。 $D_3 = (3-1)(D_2 + D_1) = 2 \times (1 + 0) = 2$。
- 根据乘法原理，总方案数为 $\binom{5}{2} \times D_3 = 10 \times 2 = 20$。
5 封信全部放错：
- 即 $D_5 = 4 \times (D_4 + D_3)$。
- 先求 $D_4 = 3 \times (D_3 + D_2) = 3 \times (2 + 1) = 9$。
- 所以 $D_5 = 4 \times (9 + 2) = 44$。

习题 3 解析：

增广矩阵表示： $$\left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \ -3 & -1 & 2 & -11 \ -2 & 1 & 2 & -3 \end{array} \right]$$
消元过程：
- 第2行加上第1行的 1.5 倍： $$R_2 \leftarrow R_2 + 1.5 R_1 \implies \left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \ 0 & 0.5 & 0.5 & 1 \ -2 & 1 & 2 & -3 \end{array} \right]$$
- 第3行加上第1行： $$R_3 \leftarrow R_3 + R_1 \implies \left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \ 0 & 0.5 & 0.5 & 1 \ 0 & 2 & 1 & 5 \end{array} \right]$$
- 交换 $R_2$ 和 $R_3$（为了数值稳定性，选取更大的主元）： $$\left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \ 0 & 2 & 1 & 5 \ 0 & 0.5 & 0.5 & 1 \end{array} \right]$$
- 第3行减去第2行的 0.25 倍： $$R_3 \leftarrow R_3 - 0.25 R_2 \implies \left[ \begin{array}{ccc|c} 2 & 1 & -1 & 8 \ 0 & 2 & 1 & 5 \ 0 & 0 & 0.25 & -0.25 \end{array} \right]$$
回代求解：
- $0.25 z = -0.25 \implies z = -1$
- $2y + z = 5 \implies 2y - 1 = 5 \implies y = 3$
- $2x + y - z = 8 \implies 2x + 3 - (-1) = 8 \implies 2x + 4 = 8 \implies x = 2$
最终解为：$x = 2, y = 3, z = -1$。可以使用前文提供的 gaussian_elimination 代码进行无缝验证。

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

提高组大纲2.2.5 数学与其他