数学基础

一、排列组合基础与计数原理

任何复杂的计数问题，剥离到最后都由加法原理和乘法原理构成。

1. 两大基本计数原理

• 加法原理（分类讨论）：完成一件事有 $n$ 类不同的方案。如果第一类有 $a_1$ 种方法，第二类有 $a_2$ 种方法，……，且这些类别之间互不重叠，那么完成这件事共有 $a_1+a_2+\dots+a_n$ 种方法。
• 乘法原理（分步进行）：完成一件事必须分为 $n$ 个连续的步骤。第一步有 $a_1$ 种方法，第二步有 $a_2$ 种方法，……，只有所有步骤全部完成，这件事才算结束。总方案数为 $a_1 \times a_2 \times \dots \times a_n$。

2. 排列 (Permutation)

定义：从 $n$ 个不同元素中，取出 $m$（$m \le n$）个元素，按照一定的顺序排成一列。

推导：第一个位置有 $n$ 种选择，第二个位置剩 $n-1$ 种选择，以此类推，第 $m$ 个位置有 $n-m+1$ 种选择。

公式：

3. 组合 (Combination)

定义：从 $n$ 个不同元素中，取出 $m$（$m \le n$）个元素组成一个集合，不考虑集合内部的顺序。

推导：在排列 $A_n^m$ 中，包含了取出的 $m$ 个元素内部的各种排列方式（共 $m!$ 种）。因为组合不关心内部顺序，所以必须除以 $m!$ 以消除重复计算。

公式：

4. 组合数的两大核心性质

性质一：对称性

物理意义：从 $n$ 个物品中选出 $m$ 个带走，其方案数等同于从 $n$ 个物品中选出 $n-m$ 个留在原地。

性质二：帕斯卡定律（杨辉三角递推）

物理意义：考虑特定的第 $n$ 个物品选与不选。如果不选，方案数为 $C_{n-1}^m$；如果必选，方案数为 $C_{n-1}^{m-1}$。利用此性质，可以通过 $O(n^2)$ 递推预处理组合数，完全规避除法操作。

5. 经典实战模型：隔板法（插板法）

要求每个对象至少分到 1 个

方程：$x_1+x_2+\dots+x_k=n$ （要求 $x_i \ge 1$）

结论：等价于在 $n-1$ 个空隙中插入 $k-1$ 块隔板，方案数为 $C_{n-1}^{k-1}$。

允许某些对象分到 0 个（最为常见）

方程：$x_1+x_2+\dots+x_k=n$ （要求 $x_i \ge 0$）

结论：给每个变量“借”一个球，使得 $y_i = x_i + 1 \ge 1$。右侧变为 $n+k$，方案数转化为 $C_{n+k-1}^{k-1}$。

二、同余数学基础与模运算律

在算法竞赛中，当答案数值超出 64 位整数（long long）的表达范围时，题目通常要求将结果对一个大整数 $p$（通常为 $10^9+7$ 或 $998244353$）取模。理解“同余”是处理此类问题的前置条件。

1. 同余的定义与本质

定义：给定一个正整数 $m$，如果两个整数 $a$ 和 $b$ 满足 $a-b$ 能够被 $m$ 整除（即 $m \mid (a-b)$），那么就称整数 $a$ 与 $b$ 对模 $m$ 同余。

数学记号：$a \equiv b \pmod m$

直观理解：$a \equiv b \pmod m$ 等价于 $a$ 除以 $m$ 的余数等于 $b$ 除以 $m$ 的余数。

举例：在日常生活的钟表（模 12）中，17 点和 5 点指向同一个位置，因此 $17 \equiv 5 \pmod{12}$。

2. 同余的三大核心运算律

同余关系在加法、减法、乘法下表现出极其优美的性质，这意味着我们可以在计算的每一步都随时取模，而不会改变最终结果。注意乘法是先算再取模，中间结果仍要装得下。

假设 $a \equiv c \pmod m$ 且 $b \equiv d \pmod m$，则：

1. 加法律：$a + b \equiv c + d \pmod m$
2. 减法律：$a - b \equiv c - d \pmod m$
3. 乘法律：$a \times b \equiv c \times d \pmod m$

3. C++ 中的取模实战规范

在 C++ 中，% 是取余运算符，但它对负数的处理与数学上的模运算不同（例如 -5 % 3 在 C++ 中等于 -2，而在纯数学中模 3 的余数应为正数 1）。因此，在代码中落实运算律时，必须遵循以下标准写法：

// 约定 0 <= a,b < mod，mod 为常用的约 10^9 级模数
// 1. 安全加法取模
int add(int a,int b){
	return (1LL*a+b)%mod;
}

// 2. 安全减法取模（绝对核心：必须加 mod 再取模，防止产生负数）
int sub(int a,int b){
	return (1LL*a-b+mod)%mod;
}

// 3. 安全乘法取模
int mul(int a,int b){
	return 1LL*a*b%mod;
}

三、模运算的除法危机与乘法逆元

1. 为什么同余没有直接的除法律？

加减乘法均可随时取模，但除法在取模意义下直接计算会导致极其荒谬的错误。

举例：计算 $6 \div 2 \pmod 5$。

实际数学结果为 $3 \pmod 5 = 3$。

如果错误地在除法中分配取模：$(6 \pmod 5) \div (2 \pmod 5) = 1 \div 2 = 0.5$，完全错误。不仅出现小数，甚至无法继续后续运算。

为了在模意义下执行“除以 $b$”的操作，我们需要找到一个数 $x$，使得乘以 $x$ 的效果等同于除以 $b$。

定义：若存在整数 $x$，满足 $b \times x \equiv 1 \pmod p$，则称 $x$ 为 $b$ 模 $p$ 的乘法逆元，通常记作 $b^{-1}$。在模 $p$ 的世界里，除以 $b$ 绝对等价于乘以 $b^{-1}$。

2. 求解逆元的两大算法

方法一：费马小定理（最常用，前提：$p$ 必须是质数）

如果 $p$ 是质数，且 $a$ 不是 $p$ 的倍数，费马小定理指出：

我们将等式左边拆分出一个 $a$：

对比逆元的定义式 $a \times x \equiv 1 \pmod p$，可以得出绝对结论：$a$ 的逆元就是 $a^{p-2}$。

只需使用快速幂算法，即可在 $O(\log p)$ 时间内求出。

模数换成合数后，有一条对应的推广——欧拉定理，见《数论工具箱》·欧拉定理。

方法二：扩展欧几里得 Exgcd（前提：$\gcd(a, p) = 1$）

裴蜀定理：扩展欧几里得的理论基础

对于不全为 $0$ 的整数 $a$ 和 $b$，设 $d=\gcd(a,b)$，则一定存在整数 $x$ 和 $y$，使得：

这就是裴蜀定理（Bézout's Identity）。进一步地，二元一次不定方程 $a \times x+b \times y=c$ 有整数解的充要条件是 $d \mid c$。

在求乘法逆元时，我们要求：

当且仅当 $\gcd(a,p)=1$ 时，裴蜀定理保证存在整数 $x,y$，使得：

两边对 $p$ 取模，就得到 $a \times x\equiv1\pmod p$。因此，扩展欧几里得算法不仅能求出 $\gcd(a,p)$，还能同时求出裴蜀定理中的系数 $x,y$，其中 $x$ 就是 $a$ 模 $p$ 的一个乘法逆元。

当模数 $p$ 不是质数时，费马小定理失效。只要 $a$ 与 $p$ 互质，就可以通过求解线性同余方程寻找逆元。

利用扩展欧几里得算法求出 $x$ 的特解，再将其平移至 $[0, p-1]$ 区间即可。

四、组合数 $O(1)$ 查询框架推导与实现

当组合数定义式 $C_n^m = \frac{n!}{m!(n-m)!}$ 需要在循环中被密集调用时（如 $10^5$ 次查询），每次用快速幂求逆元会产生 $O(Q \log p)$ 的复杂度。高频调用时，提前算好逆阶乘更省。

我们需要通过 $O(N)$ 的预处理，将单次查询降至 $O(1)$。预处理分为三步：

这里的 inv[i] 存的是 $i!$ 的逆元，不是 $i$ 的逆元；第六节批量求整数逆元用的是另一张表，不要混着用。

1. 顺序递推阶乘：fact[i] = fact[i-1] * i % mod。

2. 单次快速幂求边界逆元：直接对最大的阶乘 fact[N-1] 求解其逆元，存入 inv[N-1]。

3. 逆向递推逆元（核心黑科技）：

   由于 $\frac{1}{i!} = \frac{1}{(i+1)!} \times (i+1)$。

   映射到模意义下，可以直接得出递推式：inv[i] = inv[i+1] * (i+1) % mod。

   这样从大到小只需一次遍历，乘法即可替代所有快速幂运算。

标准化模板代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;

// 查询要求 0 <= n < N；本模板还要求 mod 为质数且 N-1 < mod
const int N=500005;
const int mod=1e9+7;

int fact[N],inv[N];

// 内部工具：快速幂
int qpow(int a,int b){
	int res=1;
	while(b){
		if(b&1)res=res*a%mod;
		a=a*a%mod;
		b>>=1;
	}
	return res;
}

// 核心：线性预处理阶乘与逆元
void init(){
	fact[0]=inv[0]=1;
	// 1. 正向预处理阶乘
	for(int i=1;i<N;i++){
		fact[i]=fact[i-1]*i%mod;
	}
	// 2. 求出最大阶乘的逆元
	inv[N-1]=qpow(fact[N-1],mod-2);
	// 3. 逆向推导所有阶乘的逆元
	for(int i=N-2;i>=1;i--){
		inv[i]=inv[i+1]*(i+1)%mod;
	}
}

// 核心：O(1) 查询组合数
int C(int n,int m){
	if(m<0||m>n||n<0)return 0;
	// C_n^m = n! * (m!)^-1 * ((n-m)!)^-1
	return fact[n]*inv[m]%mod*inv[n-m]%mod;
}

void solve(){
	// 例：查询 100 个元素中取 50 个的方案数
	cout<<C(100,50)<<'\n';
}

signed main(){
	ios::sync_with_stdio(0),cin.tie(0);
	init(); // 程序入口必须优先执行初始化
	solve();
	return 0;
}

五、极端规模环境：卢卡斯定理 (Lucas)（选学）

在少数压轴题中，会遇到极端数据规模：$n, m$ 高达 $10^{18}$ 级别，不可能开出对应的阶乘数组。但题目给定的模数 $p$ 依然是质数，且 $p \le 10^5$。

此时必须使用卢卡斯定理将规模强行降级：

物理意义与实现思维：

卢卡斯定理的本质，是将 $n$ 和 $m$ 转换为 $p$ 进制数，然后各位分别计算组合数最后相乘。在代码实现中，表现为不断将 $n$ 和 $m$ 除以 $p$ 进行递归，而每一层递归中涉及的 $n \bmod p$ 和 $m \bmod p$ 均严格小于 $p$。因此，只需预处理出大小为 $p$ 的阶乘和逆元数组即可。

标准化模板代码：

// 独立于上一节的模 1e9+7 表；p 为质数且 p <= 1e5
int p;
vector<long long> fac, invf;

long long power(long long a, long long b) {
    long long res = 1;
    while (b) {
        if (b & 1) res = res * a % p;
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

void init_lucas(int mod) {
    p = mod;
    fac.assign(p, 1);
    invf.assign(p, 1);
    for (int i = 1; i < p; i++) fac[i] = fac[i-1] * i % p;
    invf[p-1] = power(fac[p-1], p-2);
    for (int i = p-1; i >= 1; i--) invf[i-1] = invf[i] * i % p;
}

long long Csmall(int n, int m) {
    if (m > n) return 0;
    return fac[n] * invf[m] % p * invf[n-m] % p;
}

long long Lucas(long long n, long long m) {
    if (m == 0) return 1;
    return Lucas(n/p, m/p) * Csmall(n%p, m%p) % p;
}
// 使用：先 init_lucas(p)，再查询 Lucas(n,m)；更换模数必须重新初始化

关键只有一句：表算到 p-1 就停，千万别拿 p! 求逆元，它模 p 已经是 0。

六、进阶：逆元实现拓展与组合数算法选型

1. 扩展欧几里得代码实现与最小非负解

前文已经讲过，当模数 $p$ 不是质数时，我们通过解方程 $a \times x + p \times y = 1$ 来求 $a$ 模 $p$ 的逆元。这里补充落地代码和易错细节。

exgcd 求出的特解 $x$ 可能是负数。因为线性同余方程的通解相差模数 $p$ 的整数倍，为了得到合法的最小非负解，在 C++ 中需要执行一次标准的平移操作：x = (x % p + p) % p。

手算小例子： 求 $3$ 模 $5$ 的逆元（解 $3x + 5y = 1$）。 exgcd 递归到底层后回溯，最终会算出特解 $x=2, y=-1$。 验算：$3 \times 2 - 5 \times 1 = 1$。特解 $x=2$ 本身就是非负数，无需平移。若算出 $x=-3$，则 (-3 % 5 + 5) % 5 = 2。

// 求解给定 a 和模数 m 下的乘法逆元
// 输入保证：a >= 1, m >= 2 且 gcd(a, m) = 1，数值在 long long 承受范围内
// 输入样例：3 5
// 输出样例：2
#include<bits/stdc++.h>
#define int long long
using namespace std;

void exgcd(int a, int b, int &x, int &y) {
	if (b == 0) {
		x = 1;
		y = 0;
		return;
	}
	int x1, y1;
	exgcd(b, a % b, x1, y1);
	x = y1;
	y = x1 - (a / b) * y1;
}

void solve() {
	int a, m;
	if (!(cin >> a >> m)) return;
	int x, y;
	exgcd(a, m, x, y);
	
	// 转化为最小非负解
	int inv_a = x % m;
	if(inv_a < 0) inv_a += m;
	cout << inv_a << '\n';
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

2. 批量求 $1 \sim n$ 逆元的线性递推 (选学)

当题目要求求出 $1 \dots n$ 所有整数的逆元，且 $n$ 高达 $10^7$ 级别时，带 $\log$ 的做法会超时。我们需要一个 $O(n)$ 的线性递推做法。

前提条件（极其关键）： 必须满足 $1 \le n < p$ 且 $p$ 为质数。 如果 $n \ge p$，当遍历到 $i = p$ 时，$p \bmod i = 0$，代码会访问并未初始化的 inv[0]，导致 inv[p] 以及后续大量的逆元全部错误地计算为 0。若需要大于 $p$ 的数的逆元，直接让该数对 $p$ 取模，再查表即可。

递推公式与代码落地： 数学推导可得 $i^{-1} \equiv -\lfloor p/i \rfloor \times (p \bmod i)^{-1} \pmod p$。 为了避免 C++ 负数取模异常，平移一个 $p$，得到代码实现式： inv[i] = (p - p / i) * inv[p % i] % p

// 线性时间预处理 1 到 n 的所有逆元
// 输入保证：n < p, p 为质数。例如 n <= 1e7, p <= 2e9 保证乘法安全
// 输入样例：4 13
// 输出样例：1 7 9 10
#include<bits/stdc++.h>
#define int long long
using namespace std;

const int N = 10000005; // 按题目实际 n 决定，不宜过大浪费内存
int inv[N];

void solve() {
	int n, p;
	if (!(cin >> n >> p)) return;
	
	inv[1] = 1;
	cout << inv[1] << (1 == n ? "" : " ");
	for (int i = 2; i <= n; i++) {
		// (p - p / i) 防止产生负数，右侧逆元已在之前算出
		inv[i] = (p - p / i) * inv[p % i] % p;
		cout << inv[i] << (i == n ? "" : " ");
	}
	cout << '\n';
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0);
	solve();
	return 0;
}

3. 组合数算法选型指南

面对一道新题，该用哪种组合数求法？这取决于 $N, M$（组合的上下标）与 $p$（模数）的规模。

1. $N, M$ 在 $2000$ 左右，无模数或模数任意

   • 武器：杨辉三角（帕斯卡定律）$O(N^2)$ 递推。
   • 优势：纯加法操作，完全无视模数是否为质数。
   • 空间：整张表是 $O(N^2)$。到 $5000$ 时，32 位元素约需 $100$ MB，64 位元素约需 $200$ MB；能否用 32 位要看答案值域或模数，再对照题目的内存限制。
   • 注意：如果题目不要求取模，组合数增长极快，普通 long long 算不到百阶就会溢出，必须配合高精度（大整数）加法使用。

2. $N, M \le 10^7$，$p$ 为质数，且 $N < p$（最常见环境）

   • 武器：阶乘与逆阶乘 $O(N)$ 预处理，$O(1)$ 查询。
   • 限制：如果 $N \ge p$，则 $N! \bmod p = 0$，没有逆元，此路不通。

3. $N$ 极大（如 $10^9$），$M$ 较小（如 $M \le 10^5$），$p$ 为大质数

   • 武器：根据定义直接暴力计算分子分母。
   • 做法：直接套公式 $C_N^M = \frac{N(N-1)\dots(N-M+1)}{M!}$。分子暴力循环连乘 $M$ 次，分母算一次 $M!$ 后求逆元，总时间复杂度仅为 $O(M + \log p)$。不需要庞大的预处理。

4. $N, M$ 极大（如 $10^{18}$），且模数 $p$ 为小质数（$p \le 10^5$）

   • 武器：Lucas 定理。
   • 优势：它能把超大规模的组合数打散成多个小于 $p$ 的小组合数相乘，是小模数大下标时的首选武器。