C++信奥数学 - 提高组

报名

# 信奥（OI）数学进阶全套讲义大纲

---

## 1 课前说明
* **内容导读**：数学是信息学竞赛（OI）的灵魂。从普及组的简单模拟到省选的复杂数论，数学工具决定了算法的上限。
* **学习目标**：掌握 OI 竞赛中必备的数论、组合计数、容斥原理与概率期望，建立从实际问题到数学模型的抽象能力。
* **学习方法**：重理解、记模板、多刷题、强推导。

---

## 2 数论基本概念
* **整除与同余**：若 $a = qb + r$（$0 \le r < |b|$），记作 $b \mid a$。同余：$a \equiv b \pmod m$。
* **唯一分解定理（算术基本定理）**：任何大于 1 的正整数 $n$ 可唯一分解为：$n = p\_1^{c\_1} p\_2^{c\_2} \cdots p\_k^{c\_k}$。
* **约数相关**：
  * 约数个数：$\tau(n) = \prod (c\_i + 1)$
  * 约数和：$\sigma(n) = \prod \left(\sum\_{j=0}^{c\_i} p\_i^j\right)$

---

## 3 素数筛法 prime
* **试除法**：$O(\sqrt{n})$ 判断单个数是否为素数。
* **埃氏筛法**：标记每个素数的倍数，复杂度 $O(n \log \log n)$。
* **欧拉筛法（线性筛）**：保证每个合数只被其**最小质因子**筛一次，复杂度 $O(n)$。
  ```cpp
  int primes[N], cnt; bool st[N];
  void get_primes(int n) {
      for (int i = 2; i <= n; i++) {
          if (!st[i]) primes[cnt++] = i;
          for (int j = 0; primes[j] <= n / i; j++) {
              st[primes[j] * i] = true;
              if (i % primes[j] == 0) break; // 核心：线性保证
          }
      }
  }
  ```

---

## 4 欧几里得算法 gcd
* **辗转相除法**：$\gcd(a, b) = \gcd(b, a \pmod b)$。
* **代码模板**：
  ```cpp
  long long gcd(long long a, long long b) {
      return b == 0 ? a : gcd(b, a % b);
  }
  ```
* **最小公倍数**：$\text{lcm}(a, b) = \frac{a \times b}{\gcd(a, b)}$。

---

## 5 扩展欧几里得 exgcd
* **裴蜀定理**：方程 $ax + by = \gcd(a, b)$ 必然存在整数解 $(x, y)$。
* **代码模板**：
  ```cpp
  long long exgcd(long long a, long long b, long long &x, long long &y) {
      if (!b) { x = 1; y = 0; return a; }
      long long d = exgcd(b, a % b, y, x);
      y -= (a / b) * x;
      return d;
  }
  ```

---

## 6 欧拉函数 euler
* **定义**：$1 \sim n$ 中与 $n$ 互质的数的个数，记作 $\phi(n)$。
* **计算公式**：$\phi(n) = n \prod\_{p \mid n} (1 - \frac{1}{p})$。
* **线性筛求欧拉函数**：在欧拉筛素数的同时顺便递推求出所有数的欧拉函数。

---

## 7 欧拉定理
* **内容**：若 $\gcd(a, m) = 1$，则 $a^{\phi(m)} \equiv 1 \pmod m$。
* **扩展欧拉定理（降幂公式）**：用于处理高指数模幂运算 $a^b \pmod m$（$b$ 很大时可对 $\phi(m)$ 取模）。

---

## 8 乘法逆元 inv
* **定义**：若 $ax \equiv 1 \pmod m$，则 $x$ 为 $a$ 在模 $m$ 意义下的逆元 $a^{-1}$。
* **三大求法**：
  1. 费马小定理（$m$ 为素数）：$a^{m-2} \pmod m$。
  2. 扩展欧几里得解 $ax + my = 1$。
  3. 线性递推求逆元 $O(n)$。

---

## 9 中国剩余定理 crt
* **作用**：求解模数**两两互质**的一元线性同余方程组：
  $\begin{cases} x \equiv a\_1 \pmod{m\_1} \\ x \equiv a\_2 \pmod{m\_2} \\ \dots \end{cases}$
* **核心思想**：构造 $M\_i = M / m\_i$，求其逆元后加和。

---

## 9 (续) 中国剩余定理拓展版 excrt
* **作用**：模数 $m\_i$ **不保证两两互质**的同余方程组求解。
* **核心思想**：通过扩展欧几里得两两合并方程，每次合并更新解和新模数。

---

## 10 整除分块
* **作用**：快速计算形如 $\sum\_{i=1}^n \lfloor \frac{n}{i} \rfloor$ 的和式。
* **复杂度**：利用分块思想将复杂度从 $O(n)$ 优化至 $O(\sqrt{n})$。

---

## 11 什么是组合数
* **定义**：从 $n$ 个不同元素中选出 $m$ 个的方案数 $\binom{n}{m} = \frac{n!}{m!(n-m)!}$。
* **性质**：对称性 $\binom{n}{m} = \binom{n}{n-m}$；杨辉三角递推式 $\binom{n}{m} = \binom{n-1}{m-1} + \binom{n-1}{m}$。

---

## 12 二项式定理
* **公式**：$(x + y)^n = \sum\_{k=0}^n \binom{n}{k} x^{n-k} y^k$。
* **常见推论**：所有组合数之和 $\sum \binom{n}{k} = 2^n$，正负交替和为 0。

---

## 13 组合公式常见变形
* **吸取恒等式**：$m\binom{n}{m} = n\binom{n-1}{m-1}$。
* **范德蒙德卷积**：$\sum\_{k=0}^r \binom{n}{k}\binom{m}{r-k} = \binom{n+m}{r}$。

---

## 14 隔板法
* **模型一**：$n$ 个相同小球放入 $k$ 个不同盒子，每盒非空，方案数 $\binom{n-1}{k-1}$。
* **模型二**：允许空盒时（可空隔板法），方案数 $\binom{n+k-1}{k-1}$。

---

## 15 错位排列
* **定义**：没有任何一个元素处于自己原本位置的排列数 $D\_n$。
* **递推公式**：$D\_n = (n-1)(D\_{n-1} + D\_{n-2})$，且 $D\_1 = 0, D\_2 = 1$。

---

## 16 圆排列与多重集合的排列组合
* **圆排列**：$n$ 个不同元素围成一圈的排列数：$Q\_n = (n-1)!$。
* **多重集合排列**：包含相同元素的集合全排列公式：$\frac{(\sum c\_i)!}{c\_1! c\_2! \cdots c\_k!}$。

---

## 17 康托展开 Cantor
* **作用**：实现全排列与其字典序排名之间的双向高效转换（通常结合树状数组 $O(n \log n)$）。
* **公式**：$\text{Rank} = 1 + \sum a\_i \cdot (n-i)!$。

---

## 18 斯特林数 stirling
* **第一类斯特林数**：$S\_1(n, k)$，将 $n$ 个不同元素构成 $k$ 个圆排列的方案数。
* **第二类斯特林数**：$S\_2(n, k)$，将 $n$ 个不同元素划分到 $k$ 个相同非空集合的方案数。

---

## 19 卡特兰数基础 catalan
* **通项公式**：$C\_n = \frac{1}{n+1}\binom{2n}{n}$。
* **递推公式**：$C\_n = \sum\_{i=0}^{n-1} C\_i C\_{n-1-i}$。
* **经典模型**：合法括号序列、进出栈顺序、二叉树形态。

---

## 20 卡特兰数应用
* **网格路径不越界问题**：从 $(0,0)$ 到 $(n,n)$ 不穿过对角线 $y=x$ 的路径数。
* 复杂竞赛变式题型的抽象与转化技巧。

---

## 21 放球问题汇总
* **经典“八大模型”全景梳理**：系统归纳“球同/异、盒同/异、空/非空”的组合计数终极表格。

---

## 22 卢卡斯定理 lucas
* **作用**：当模数 $p$ 是较小素数，而 $n, m$ 很大时，快速计算组合数对 $p$ 取模的结果：
  $$\binom{n}{m} \equiv \binom{n \pmod p}{m \pmod p} \cdot \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \pmod p$$

---

## 23 容斥原理
* **公式表达**：$|A\_1 \cup A\_2 \cup \dots \cup A\_n| = \sum |A\_i| - \sum |A\_i \cap A\_j| + \dots + (-1)^{n-1} |A\_1 \cap \dots \cap A\_n|$。
* **OI应用**：结合二进制状态压缩或 DFS 处理“满足至少/至多一个条件”的计数问题。

---

## 24 概率与期望
* **基础概念**：离散型随机变量的概率和数学期望 $E(X) = \sum x\_i P(X = x\_i)$。
* **全期望公式与线性性质**：$E(X + Y) = E(X) + E(Y)$（期望的线性性在 DP 中的降维打击应用）。
* **图上随机游走与概率 DP**：结合高斯消元或拓扑排序求解复杂博弈与概率问题。