レム・咲く夜

LemuSakuya的个人博客网站堂堂登场

这一天终于来到了！！经过长期的策划以及愚蠢的大创项目策划书的拖延，我终于部署好了我的个人博客，真的很感谢Mizuki，用这么好的模版让我舒爽一整天！！！

標籤

レム・咲く夜

LemuSakuya的个人博客网站堂堂登场

这一天终于来到了！！经过长期的策划以及愚蠢的大创项目策划书的拖延，我终于部署好了我的个人博客，真的很感谢Mizuki，用这么好的模版让我舒爽一整天！！！

標籤

レム・咲く夜

LemuSakuya的个人博客网站堂堂登场

这一天终于来到了！！经过长期的策划以及愚蠢的大创项目策划书的拖延，我终于部署好了我的个人博客，真的很感谢Mizuki，用这么好的模版让我舒爽一整天！！！

標籤

🌸 咲夜の秘密メロディ

分類

站點統計

文章

79

分類

16

標籤

24

總字數

394,971

運行天數

0 天

最後活動

0 天前

11706 字

31 分鐘

数学算法与组合计数

2026-06-03

Algorithm

Study Notes

/

Algorithm

第 10 章数学算法与组合计数#

本章目标：掌握算法题中最常见的数论、组合计数、概率期望和矩阵快速幂工具。

10.1 学习目标#

掌握 gcd、扩展欧几里得、快速幂和逆元。
掌握质数筛和质因数分解。
掌握组合数预处理和常见计数方法。
理解容斥原理和期望线性性。
掌握矩阵快速幂处理线性递推。

10.2 最大公约数#

欧几里得算法：

\gcd(a,b)=\gcd(b, a \bmod b)

终止条件：

\gcd(a,0)=a

复杂度： $O(\log \min(a,b))$ 。

10.3 扩展欧几里得#

求整数 x, y 满足：

ax+by=\gcd(a,b)

当 $\gcd(a,m)=1$ 时，x 是 a 在模 m 意义下的逆元：

a x \equiv 1 \pmod m

10.4 快速幂与逆元#

快速幂：

a^b \bmod p

若 p 是质数且 a 不是 p 的倍数，根据费马小定理：

a^{p-1}\equiv 1 \pmod p

所以：

a^{-1}\equiv a^{p-2} \pmod p

10.5 质数筛#

埃氏筛：

1
vector<bool> is_prime(n + 1, true);
2
is_prime[0] = is_prime[1] = false;
3
for (int i = 2; i * i <= n; i++) {
4
    if (is_prime[i]) {
5
        for (int j = i * i; j <= n; j += i) is_prime[j] = false;
6
    }
7
}

复杂度约为 $O(n\log\log n)$ 。

线性筛可以保证每个合数只被最小质因子筛一次。

10.6 组合数#

组合数定义：

C(n,k)=\frac{n!}{k!(n-k)!}

递推：

C(n,k)=C(n-1,k)+C(n-1,k-1)

模质数 p 时可预处理阶乘和逆元：

C(n,k)=fac[n]\cdot invfac[k]\cdot invfac[n-k] \bmod p

10.7 容斥原理#

两个集合：

|A\cup B|=|A|+|B|-|A\cap B|

三个集合：

|A\cup B\cup C|=|A|+|B|+|C|-|A\cap B|-|A\cap C|-|B\cap C|+|A\cap B\cap C|

一般形式：

\left|\bigcup_{i=1}^{n} A_i\right| = \sum_{\emptyset \ne S \subseteq \{1..n\}} (-1)^{|S|+1} \left|\bigcap_{i\in S} A_i\right|

10.8 期望线性性#

无论变量是否独立，都有：

E[X+Y]=E[X]+E[Y]

更一般：

E\left[\sum_i X_i\right]=\sum_i E[X_i]

很多计数期望题可以把总量拆成指示变量：

X_i=\begin{cases}1,& \text{事件 i 发生}\\0,& \text{否则}\end{cases}

则：

E[X_i]=P(X_i=1)

10.9 矩阵快速幂#

斐波那契数列：

F_n=F_{n-1}+F_{n-2}

可写成矩阵：

\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}

因此：

\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}

用快速幂可在 $O(k^3\log n)$ 处理 k 阶线性递推。

10.10 易错点#

取模除法不能直接除，要乘逆元。
逆元存在条件是互质。
快速幂乘法溢出。
组合数 k 小于 0 或大于 n 时应为 0。
容斥符号写反。
期望题误以为必须独立。

10.11 练习#

实现 gcd 和扩展 gcd。
预处理 $C(n,k) \bmod p$ 。
用容斥计算不被若干数整除的个数。
用期望线性性求随机排列逆序对期望。
用矩阵快速幂求斐波那契第 n 项。

ACM/OI 扩展：数论模板与组合套路#

本节补充 OIer 和 ACMer 常用的算法套路、模板、复杂度分析和易错点。写模板时默认使用 C++17，变量名尽量短，但注释要说明不变量和适用条件。

1. 快速幂模板#

支持大指数取模，使用 __int128 防止乘法溢出。

1
long long qpow(long long a, long long b, long long mod) {
2
    long long r = 1 % mod;
3
    while (b) {
4
        if (b & 1) r = (__int128)r * a % mod;
5
        a = (__int128)a * a % mod;
6
        b >>= 1;
7
    }
8
    return r;
9
}

要点：

模数为 1 时答案为 0。
指数可能是 long long。

2. 扩展 gcd#

求 $ax+by=gcd(a,b)$ 。

1
long long exgcd(long long a, long long b, long long& x, long long& y) {
2
    if (!b) { x = 1; y = 0; return a; }
3
    long long x1, y1;
4
    long long g = exgcd(b, a % b, x1, y1);
5
    x = y1;
6
    y = x1 - a / b * y1;
7
    return g;
8
}

要点：

线性同余方程有解条件： $gcd(a,m)$ 整除 b。
逆元存在条件： $gcd(a,m)=1$ 。

3. 线性筛#

每个合数只被最小质因子筛掉一次。

1
vector<int> primes, isComp(n + 1);
2
for (int i = 2; i <= n; ++i) {
3
    if (!isComp[i]) primes.push_back(i);
4
    for (int p : primes) {
5
        if (1LL * i * p > n) break;
6
        isComp[i * p] = 1;
7
        if (i % p == 0) break;
8
    }
9
}

要点：

可顺便求最小质因子、欧拉函数、莫比乌斯函数。

4. 组合数预处理#

模数为质数且 n 较大、询问多时使用。

1
vector<long long> fac(n + 1), ifac(n + 1);
2
fac[0] = 1;
3
for (int i = 1; i <= n; ++i) fac[i] = fac[i - 1] * i % mod;
4
ifac[n] = qpow(fac[n], mod - 2, mod);
5
for (int i = n; i >= 1; --i) ifac[i - 1] = ifac[i] * i % mod;
6
auto C = [&](int n, int k) -> long long {
7
    if (k < 0 || k > n) return 0;
8
    return fac[n] * ifac[k] % mod * ifac[n - k] % mod;
9
};

要点：

只适用于模数为质数或逆元存在。
多次询问非常高效。

5. 中国剩余定理 CRT#

求解同余方程组。

x \equiv a_i \pmod {m_i}

要点：

模数两两互质时可用经典 CRT。
不互质时要用扩展 CRT，检查差值是否能被 gcd 整除。

训练题型：

合并两个同余方程。
用 CRT 处理周期相遇问题。

本章模板背诵清单#

能在 5 分钟内写出本章第一个核心模板。
能说出每个模板的时间复杂度和空间复杂度。
能说明模板不适用的反例。
能为模板构造 3 个边界样例。
能把模板改成 0-index 或 1-index 版本。

组合数与数论进阶#

Lucas 定理#

模数 p 为质数，n、k 很大时计算组合数。

C(n,k) \equiv C(\lfloor n/p\rfloor,\lfloor k/p\rfloor) C(n\bmod p,k\bmod p) \pmod p

1
long long lucas(long long n, long long k, long long p) {
2
    if (k < 0 || k > n) return 0;
3
    if (k == 0) return 1;
4
    return lucas(n / p, k / p, p) * C(n % p, k % p) % p;
5
}

需要预处理 0..p-1 的组合数。
p 太大时不适合直接预处理。

欧拉函数#

$\varphi(n)$ 表示 1..n 中与 n 互质的数的个数。

\varphi(n)=n\prod_{p|n}(1-\frac1p)

线性筛可同时求 phi。
欧拉定理：若 gcd(a,m)=1，则 $a^{\varphi(m)}\equiv1\pmod m$ 。

莫比乌斯函数#

用于互质计数、反演。

$\mu(n)=0$ 若 n 含平方因子。
$\mu(n)=(-1)^k$ 若 n 是 k 个不同质数乘积。
常与整除分块结合。

整除分块#

当 $\lfloor n/i\rfloor$ 取值只有 $O(\sqrt n)$ 种时使用。

1
for (long long l = 1, r; l <= n; l = r + 1) {
2
    long long q = n / l;
3
    r = n / q;
4
    // i in [l, r] have same floor(n / i) = q
5
}

常用于求和 $\sum f(\lfloor n/i\rfloor)$ 。

Burnside 引理入门#

计数在对称变换下不同的对象数量。

\text{orbits}=\frac{1}{|G|}\sum_{g\in G} fix(g)

项链染色、旋转等价常用。
先列出群操作，再数每个操作固定的方案。

高频模板训练卡#

这一组训练卡用于把“10_数学算法与组合计数”转化为赛场识别能力。每张卡都包含题目信号、模板选择、复杂度、反例和实现检查。

卡 1：快速幂#

题目信号：题目含模数、整除、计数、概率、递推或快速幂。
优先模板：优先考虑快速幂。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为快速幂写公式来源和一个最小代码模板。

卡 2：扩展 gcd#

题目信号：题目含模数、整除、计数、概率、递推或扩展 gcd。
优先模板：优先考虑扩展 gcd。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为扩展 gcd 写公式来源和一个最小代码模板。

卡 3：线性同余#

题目信号：题目含模数、整除、计数、概率、递推或线性同余。
优先模板：优先考虑线性同余。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为线性同余写公式来源和一个最小代码模板。

卡 4：逆元#

题目信号：题目含模数、整除、计数、概率、递推或逆元。
优先模板：优先考虑逆元。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为逆元写公式来源和一个最小代码模板。

卡 5：埃氏筛#

题目信号：题目含模数、整除、计数、概率、递推或埃氏筛。
优先模板：优先考虑埃氏筛。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为埃氏筛写公式来源和一个最小代码模板。

卡 6：线性筛#

题目信号：题目含模数、整除、计数、概率、递推或线性筛。
优先模板：优先考虑线性筛。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为线性筛写公式来源和一个最小代码模板。

卡 7：欧拉函数#

题目信号：题目含模数、整除、计数、概率、递推或欧拉函数。
优先模板：优先考虑欧拉函数。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为欧拉函数写公式来源和一个最小代码模板。

卡 8：莫比乌斯函数#

题目信号：题目含模数、整除、计数、概率、递推或莫比乌斯函数。
优先模板：优先考虑莫比乌斯函数。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为莫比乌斯函数写公式来源和一个最小代码模板。

卡 9：组合数预处理#

题目信号：题目含模数、整除、计数、概率、递推或组合数预处理。
优先模板：优先考虑组合数预处理。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为组合数预处理写公式来源和一个最小代码模板。

卡 10：Lucas 定理#

题目信号：题目含模数、整除、计数、概率、递推或 Lucas 定理。
优先模板：优先考虑 Lucas 定理。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为 Lucas 定理写公式来源和一个最小代码模板。

卡 11：CRT#

题目信号：题目含模数、整除、计数、概率、递推或 CRT。
优先模板：优先考虑 CRT。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为 CRT 写公式来源和一个最小代码模板。

卡 12：扩展 CRT#

题目信号：题目含模数、整除、计数、概率、递推或扩展 CRT。
优先模板：优先考虑扩展 CRT。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为扩展 CRT 写公式来源和一个最小代码模板。

卡 13：容斥原理#

题目信号：题目含模数、整除、计数、概率、递推或容斥原理。
优先模板：优先考虑容斥原理。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为容斥原理写公式来源和一个最小代码模板。

卡 14：期望线性性#

题目信号：题目含模数、整除、计数、概率、递推或期望线性性。
优先模板：优先考虑期望线性性。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为期望线性性写公式来源和一个最小代码模板。

卡 15：矩阵快速幂#

题目信号：题目含模数、整除、计数、概率、递推或矩阵快速幂。
优先模板：优先考虑矩阵快速幂。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为矩阵快速幂写公式来源和一个最小代码模板。

卡 16：整除分块#

题目信号：题目含模数、整除、计数、概率、递推或整除分块。
优先模板：优先考虑整除分块。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为整除分块写公式来源和一个最小代码模板。

卡 17：Burnside#

题目信号：题目含模数、整除、计数、概率、递推或 Burnside。
优先模板：优先考虑 Burnside。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为 Burnside 写公式来源和一个最小代码模板。

卡 18：Polya 入门#

题目信号：题目含模数、整除、计数、概率、递推或 Polya 入门。
优先模板：优先考虑 Polya 入门。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为 Polya 入门写公式来源和一个最小代码模板。

卡 19：高斯消元#

题目信号：题目含模数、整除、计数、概率、递推或高斯消元。
优先模板：优先考虑高斯消元。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为高斯消元写公式来源和一个最小代码模板。

卡 20：素性测试 MillerRabin#

题目信号：题目含模数、整除、计数、概率、递推或素性测试 MillerRabin。
优先模板：优先考虑素性测试 MillerRabin。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为素性测试 MillerRabin 写公式来源和一个最小代码模板。

卡 21：Pollard Rho#

题目信号：题目含模数、整除、计数、概率、递推或 Pollard Rho。
优先模板：优先考虑 Pollard Rho。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为 Pollard Rho 写公式来源和一个最小代码模板。

卡 22：博弈 SG#

题目信号：题目含模数、整除、计数、概率、递推或博弈 SG。
优先模板：优先考虑博弈 SG。
核心不变量：数学变形保持等价，取模运算满足存在条件。
复杂度目标：多数数论模板 O(log n) 或 O(n log log n)，组合预处理 O(n)。
不适用场景：模数非质数却使用费马逆元、变量不互质时不适用。
实现检查：检查负数取模、乘法溢出、组合数非法 k、gcd 条件。
边界样例：模数 1、k<0、k>n、a=0、n 很大。
训练题型：为博弈 SG 写公式来源和一个最小代码模板。

本章赛前默写任务#

10_数学算法与组合计数：详细训练清单#

本清单用于把章节知识拆成可执行的小任务，偏 OI/ACM 赛场使用。

训练点 1：快速幂#

识别信号：题面出现与“快速幂”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“快速幂”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 2：扩展 gcd#

识别信号：题面出现与“扩展 gcd”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“扩展 gcd”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 3：线性同余#

识别信号：题面出现与“线性同余”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“线性同余”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 4：逆元#

识别信号：题面出现与“逆元”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“逆元”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 5：埃氏筛#

识别信号：题面出现与“埃氏筛”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“埃氏筛”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 6：线性筛#

识别信号：题面出现与“线性筛”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“线性筛”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 7：欧拉函数#

识别信号：题面出现与“欧拉函数”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“欧拉函数”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 8：莫比乌斯函数#

识别信号：题面出现与“莫比乌斯函数”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“莫比乌斯函数”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 9：组合数#

识别信号：题面出现与“组合数”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“组合数”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 10：Lucas 定理#

识别信号：题面出现与“Lucas 定理”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Lucas 定理”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 11：CRT#

识别信号：题面出现与“CRT”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“CRT”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 12：扩展 CRT#

识别信号：题面出现与“扩展 CRT”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“扩展 CRT”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 13：容斥#

识别信号：题面出现与“容斥”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“容斥”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 14：期望线性性#

识别信号：题面出现与“期望线性性”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“期望线性性”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 15：矩阵快速幂#

识别信号：题面出现与“矩阵快速幂”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“矩阵快速幂”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 16：整除分块#

识别信号：题面出现与“整除分块”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“整除分块”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 17：Burnside#

识别信号：题面出现与“Burnside”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“Burnside”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 18：SG 函数#

识别信号：题面出现与“SG 函数”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“SG 函数”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 19：快速幂#

识别信号：题面出现与“快速幂”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“快速幂”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 20：扩展 gcd#

识别信号：题面出现与“扩展 gcd”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“扩展 gcd”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

训练点 21：线性同余#

识别信号：题面出现与“线性同余”相关的限制、操作或查询时，先判断能否套用本章模型。
建模步骤：写出输入对象、维护状态、允许操作、目标答案，再决定使用暴力、模板或优化。
模板要求：能默写核心代码，并说明变量含义、初始化方式和循环边界。
复杂度要求：写出预处理、单次操作、总复杂度，并确认能通过最大数据范围。
反例检查：构造最小规模、全相等、极端值、重复值、无解或刚好可行的样例。
复盘要求：若做错，记录错因是建模、证明、复杂度、边界、溢出还是模板不熟。
扩展任务：把“线性同余”与至少一个其他专题组合，例如二分、图论、DP、数据结构或数学。

如果這篇文章對你有幫助，歡迎分享給更多人！

数学算法与组合计数

https://lemusakuya.com/posts/study-notes/algorithm/10_数学算法与组合计数/

作者

レム・咲く夜

發布於

2026-06-03

許可協議

部分資訊可能已經過時

相關文章智能推薦

Algorithm 《算法》学习笔记：01_算法学习总览与复杂度分析

2

算法设计与分析完全学习手册

Algorithm 《算法》学习总览与学习路线

3

字符串算法

Algorithm 《算法》学习笔记：09_字符串算法

4

树与图论基础

Algorithm 《算法》学习笔记：07_树与图论基础

5

基础数据结构与语言工具

Algorithm 《算法》学习笔记：02_基础数据结构与语言工具

隨機文章隨機推薦

1

渗透测试方法论

Cybersecurity 2026-04-27

Digital Image Processing 2026-04-27

4

数码管与矩阵键盘

MCU Development 2026-04-27

5

I2C、SPI与常见外设

MCU Development 2026-04-27

ぬくぬくうちにゃ💤

第 10 章 数学算法与组合计数#

10.1 学习目标#

10.2 最大公约数#

10.3 扩展欧几里得#

10.4 快速幂与逆元#

10.5 质数筛#

10.6 组合数#

10.7 容斥原理#

10.8 期望线性性#

10.9 矩阵快速幂#

10.10 易错点#

10.11 练习#

ACM/OI 扩展：数论模板与组合套路#

1. 快速幂模板#

2. 扩展 gcd#

3. 线性筛#

4. 组合数预处理#

5. 中国剩余定理 CRT#

本章模板背诵清单#

组合数与数论进阶#

Lucas 定理#

欧拉函数#

莫比乌斯函数#

整除分块#

Burnside 引理入门#

高频模板训练卡#

卡 1：快速幂#

卡 2：扩展 gcd#

卡 3：线性同余#

卡 4：逆元#

卡 5：埃氏筛#

卡 6：线性筛#

卡 7：欧拉函数#

卡 8：莫比乌斯函数#

卡 9：组合数预处理#

卡 10：Lucas 定理#

卡 11：CRT#

卡 12：扩展 CRT#

卡 13：容斥原理#

卡 14：期望线性性#

卡 15：矩阵快速幂#

卡 16：整除分块#

卡 17：Burnside#

卡 18：Polya 入门#

卡 19：高斯消元#

卡 20：素性测试 MillerRabin#

卡 21：Pollard Rho#

卡 22：博弈 SG#

本章赛前默写任务#

10_数学算法与组合计数：详细训练清单#

训练点 1：快速幂#

训练点 2：扩展 gcd#

训练点 3：线性同余#

训练点 4：逆元#

训练点 5：埃氏筛#

训练点 6：线性筛#

训练点 7：欧拉函数#

训练点 8：莫比乌斯函数#

训练点 9：组合数#

训练点 10：Lucas 定理#

训练点 11：CRT#

训练点 12：扩展 CRT#

训练点 13：容斥#

训练点 14：期望线性性#

训练点 15：矩阵快速幂#

训练点 16：整除分块#

训练点 17：Burnside#

训练点 18：SG 函数#

训练点 19：快速幂#

训练点 20：扩展 gcd#

训练点 21：线性同余#

目錄

第 10 章数学算法与组合计数#