📎 附录 E
⏱️ 约 50 分钟
🎯 参考资料
数学
💡 关于本附录： 算法竞赛中经常需要用到基础算术之外的数学工具。本附录涵盖 USACO Bronze、Silver、Gold 中常见的核心数学知识，并为每个主题提供可直接用于竞赛的代码模板。
很多题目要求输出"答案对 10⁹ + 7 取模"的结果。这并非随意为之——它是为了在答案极其庞大时防止整数溢出 。
举个例子："N 个元素的排列有多少种？"答案是 N!。当 N = 20 时，N! = 2,432,902,008,176,640,000，已超过 long long 的最大值（约 9.2 × 10¹⁸）。当 N = 100 时，根本无法表示。
解决方案： 对一个素数 M（通常取 10⁹ + 7）取模，将所有运算在模意义下进行。
(a + b) mod M = ((a mod M) + (b mod M)) mod M
(a × b) mod M = ((a mod M) × (b mod M)) mod M
(a - b) mod M = ((a mod M) - (b mod M) + M) mod M ← 注意加上 M！
时钟类比与关键性质——记住每次算术运算后都要取模：
常量 数值 为何选这个值？
1e9 + 71,000,000,007 素数，适合 int（< 2³¹），使用最广泛 1e9 + 91,000,000,009 素数，1e9+7 的备选 998244353998,244,353 NTT 友好素数（用于多项式运算）
📄 查看代码：基础模运算模板
// 解答：模运算基础
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll MOD = 1e9 + 7; // 竞赛编程标准模数
// 安全加法：(a + b) % MOD
ll addMod(ll a, ll b) {
return (a % MOD + b % MOD) % MOD;
}
// 安全减法：(a - b + MOD) % MOD（处理负数结果）
ll subMod(ll a, ll b) {
return ((a % MOD) - (b % MOD) + MOD) % MOD; // 加 MOD 防止负数！
}
// 安全乘法：(a * b) % MOD
// 关键：a 和 b 最大为 MOD-1 ≈ 10^9，乘积 ≈ 10^18 在 long long 范围内
ll mulMod(ll a, ll b) {
return (a % MOD) * (b % MOD) % MOD;
}
// 示例：计算前 N 个正整数之和 mod MOD
ll sumFirstN(ll n) {
// 公式 n*(n+1)/2，但除法需要用模逆元
// 暂时用逐步累加：
ll result = 0;
for (ll i = 1; i <= n; i++) {
result = addMod(result, i);
}
return result;
}
⚠️ 致命 Bug： 在 C++ 中，若 a < b，(a - b) % MOD 可能为负数 ！请始终写成 (a - b + MOD) % MOD。
朴素方式计算 a^n mod M 需要 O(N) 次乘法。快速幂（反复平方法）只需 O(log N)
核心思路：a^n = a^(n/2) × a^(n/2) 若 n 为偶数
a^n = a × a^((n-1)/2) × a^((n-1)/2) 若 n 为奇数
示例：a^13 = a^(1101₂)
= a^8 × a^4 × a^1
= 3 次乘法，而非 12 次！
📄 C++ 完整代码
// 解答：模意义快速幂 — O(log n)
// 计算 (base^exp) % mod
ll power(ll base, ll exp, ll mod = MOD) {
ll result = 1;
base %= mod; // 先对底数取模
while (exp > 0) {
if (exp & 1) { // 若当前位为 1
result = result * base % mod;
}
base = base * base % mod; // 底数平方
exp >>= 1; // 移动到下一位
}
return result;
}
// 使用示例：
// power(2, 10) = 1024 % MOD = 1024
// power(2, 100, MOD) = 2^100 mod (10^9+7)
a 对模 M 的模逆元 是一个数 a⁻¹，满足 a × a⁻¹ ≡ 1 (mod M)。
这让我们可以进行模意义下的除法 ：a / b mod M = a × b⁻¹ mod M。
费马小定理： 若 M 为素数且 gcd(a, M) = 1，则：
a^(M-1) ≡ 1 (mod M)
⟹ a^(M-2) ≡ a⁻¹ (mod M)
📄
// 解答：利用费马小定理求模逆元
// 仅在 MOD 为素数且 gcd(a, MOD) = 1 时适用
ll modInverse(ll a, ll mod = MOD) {
return power(a, mod - 2, mod);
}
// 模意义下的除法：
ll divMod(ll a, ll b) {
return mulMod(a, modInverse(b));
}
// 示例：(n! / k!) mod MOD
// = n! × (k!)^(-1) mod MOD
// = n! × modInverse(k!) mod MOD
对于需要多次计算组合数 C(n, k) 的题目：
📄 对于需要多次计算组合数 `C(n, k)` 的题目：
// 解答：预处理阶乘，O(1) 查询组合数
const int MAXN = 1000005;
ll fact[MAXN], inv_fact[MAXN];
void precompute() {
fact[0] = 1;
for (int i = 1; i < MAXN; i++) {
fact[i] = fact[i-1] * i % MOD;
}
inv_fact[MAXN-1] = modInverse(fact[MAXN-1]);
for (int i = MAXN-2; i >= 0; i--) {
inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}
}
// C(n, k) = n! / (k! * (n-k)!)
ll C(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}
// 用法：调用一次 precompute()，之后 C(n, k) 均为 O(1)
两个数的最大公因数 （GCD）是能同时整除两者的最大整数。
欧几里得算法： 基于 gcd(a, b) = gcd(b, a % b)。
每次递归调用都会缩小问题规模，逐步推导的过程一目了然：
📄 
// 解答：GCD — O(log(min(a,b)))
int gcd(int a, int b) {
while (b != 0) {
a %= b;
swap(a, b);
}
return a;
}
// 递归写法：
// int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); }
// C++17：<numeric> 中的 std::gcd
// int g = gcd(a, b); // std::gcd，C++17（推荐）
// int g = __gcd(a, b); // 旧版 GCC 内建函数，仍可用
追踪示例： gcd(48, 18)：
gcd(48, 18) → gcd(18, 48%18=12) → gcd(12, 18%12=6) → gcd(6, 0) = 6
📄 查看代码：LCM 与溢出陷阱
// 解答：LCM — 注意溢出！
// 错误写法：大数相乘时溢出
long long lcmWrong(long long a, long long b) {
return a * b / gcd(a, b); // a*b 即使是 long long 也可能溢出！
}
// 正确写法：先除后乘
long long lcm(long long a, long long b) {
return a / gcd(a, b) * b; // 先除再乘
}
// a / gcd(a,b) 一定是整数，不损失精度
// 然后乘以 b：最大约 10^18，在 long long 范围内
lcm(a, b) = a × b / gcd(a, b) = (a / gcd(a, b)) × b
⚠️ 始终先除后乘 ，避免溢出！
找整数 x, y 满足 ax + by = gcd(a, b)——在 MOD 不是素数时计算模逆元非常有用：
📄 找整数 x, y 满足 `ax + by = gcd(a, b)`——在 MOD 不是素数时计算模逆元非常有用：
// 解答：扩展欧几里得算法 — O(log(min(a,b)))
// 返回 gcd(a,b)，并设置 x,y 使得 a*x + b*y = gcd(a,b)
long long extgcd(long long a, long long b, long long &x, long long &y) {
if (b == 0) { x = 1; y = 0; return a; }
long long x1, y1;
long long g = extgcd(b, a % b, x1, y1);
x = y1;
y = x1 - (a / b) * y1;
return g;
}
// 使用 extgcd 求模逆元（即使 MOD 不是素数也适用）：
long long modInverseExtGcd(long long a, long long mod) {
long long x, y;
long long g = extgcd(a, mod, x, y);
if (g != 1) return -1; // 无逆元（gcd != 1）
return (x % mod + mod) % mod;
}
📄 查看代码：试除法
// 解答：试除法判素 — O(sqrt(N))
bool isPrime(long long n) {
if (n < 2) return false;
if (n == 2) return true;
if (n % 2 == 0) return false;
for (long long i = 3; i * i <= n; i += 2) {
if (n % i == 0) return false;
}
return true;
}
// 高效原因：若 n 有大于 sqrt(n) 的因子，必然也有小于等于 sqrt(n) 的因子
// 只检查 2 之后的奇数（迭代次数减半）
高效找出 N 以内的所有质数：
📄 高效找出 N 以内的所有质数：
// 解答：埃筛 — O(N log log N) 时间，O(N) 空间
// 运行后，isPrime[i] = true 当且仅当 i 是质数
const int MAXN = 1000005;
bool isPrime[MAXN];
void sieve(int n) {
fill(isPrime, isPrime + n + 1, true); // 初始假设全是质数
isPrime[0] = isPrime[1] = false; // 0 和 1 不是质数
for (int i = 2; (long long)i * i <= n; i++) {
if (isPrime[i]) {
// 标记 i 的所有倍数为合数
for (int j = i * i; j <= n; j += i) {
isPrime[j] = false;
// 从 i*i 开始（更小的倍数已被更小的素数标记过）
}
}
}
}
// 统计 N 以内的质数个数：
void countPrimes(int n) {
sieve(n);
int count = 0;
for (int i = 2; i <= n; i++) {
if (isPrime[i]) count++;
}
cout << count << "\n";
}
为什么内层循环从 i² 开始？ i 的所有小于 i² 的倍数（如 2i, 3i, ..., (i-1)i）已被更小的质数（2, 3, ..., i-1）标记过。从 i² 开始可以避免冗余操作。
欧拉筛确保每个合数只被标记一次：
📄 欧拉筛确保每个合数只被标记一次：
// 解答：线性筛（欧拉筛）— O(N) 时间
// 同时计算每个数的最小质因子（SPF）
const int MAXN = 1000005;
int spf[MAXN]; // 最小质因子
vector<int> primes;
void linearSieve(int n) {
fill(spf, spf + n + 1, 0);
for (int i = 2; i <= n; i++) {
if (spf[i] == 0) { // i 是质数
spf[i] = i;
primes.push_back(i);
}
for (int j = 0; j < (int)primes.size() && primes[j] <= spf[i] && (long long)i * primes[j] <= n; j++) {
spf[i * primes[j]] = primes[j]; // 标记合数
}
}
}
// 利用 SPF 快速分解质因数：
// 每次分解 O(log N)
vector<int> factorize(int n) {
vector<int> factors;
while (n > 1) {
factors.push_back(spf[n]);
n /= spf[n];
}
return factors;
}
📄 查看代码：基本位操作
// 解答：常用位运算参考
int n = 42; // 二进制：101010
// ── AND（&）：两位都为 1 才为 1 ──
int a = 6 & 3; // 110 & 011 = 010 = 2
// ── OR（|）：至少一位为 1 则为 1 ──
int b = 6 | 3; // 110 | 011 = 111 = 7
// ── XOR（^）：恰好一位为 1 才为 1 ──
int c = 6 ^ 3; // 110 ^ 011 = 101 = 5
// ── NOT（~）：翻转所有位（补码） ──
int d = ~6; // = -7（补码表示）
// ── 左移（<<）：乘以 2^k ──
int e = 1 << 4; // = 16 = 2^4
// ── 右移（>>）：除以 2^k（算术右移） ──
int f = 32 >> 2; // = 8 = 32/4
📄 查看代码：竞赛常用位运算技巧
// 解答：竞赛编程位运算技巧
// ── 判断 n 是否为奇数 ──
bool isOdd(int n) { return n & 1; } // 最低位为 1 当且仅当 n 为奇数
// ── 判断 n 是否为 2 的幂次 ──
bool isPow2(int n) { return n > 0 && (n & (n-1)) == 0; }
// 原因：2 的幂次：1=001, 2=010, 4=100。n-1 会翻转所有低位。
// 4 & 3 = 100 & 011 = 000。非 2 的幂次：6 & 5 = 110 & 101 = 100 ≠ 0。
// ── 取第 k 位（从右 0 开始计数） ──
bool getBit(int n, int k) { return (n >> k) & 1; }
// ── 将第 k 位置 1 ──
int setBit(int n, int k) { return n | (1 << k); }
// ── 将第 k 位清零 ──
int clearBit(int n, int k) { return n & ~(1 << k); }
// ── 翻转第 k 位 ──
int toggleBit(int n, int k) { return n ^ (1 << k); }
// ── lowbit：最低位的 1（树状数组中常用！） ──
int lowbit(int n) { return n & (-n); }
// 示例：lowbit(12) = lowbit(1100) = 0100 = 4
// ── 统计置位数（popcount） ──
int popcount(int n) { return __builtin_popcount(n); } // 使用内建函数！
// long long 版本：__builtin_popcountll(n)
// ── 不用临时变量交换两数 ──
void swapXOR(int &a, int &b) {
a ^= b;
b ^= a;
a ^= b;
}
// （通常直接用 std::swap——这主要是一个技巧性写法）
// ── 找最低位 1 的位置 ──
int lowestBitPos(int n) { return __builtin_ctz(n); } // 统计尾部零个数
// __builtin_clz(n) = 统计前导零个数
一个强大的技巧：用位掩码枚举集合的所有子集。
📄 一个强大的技巧：用位掩码枚举集合的所有子集。
// 解答：位掩码子集枚举
// 枚举 N 元素集合的所有子集
void enumerateAllSubsets(int n) {
// 共 2^n 个子集
for (int mask = 0; mask < (1 << n); mask++) {
// mask 表示一个子集：第 i 位为 1 表示包含元素 i
cout << "子集: {";
for (int i = 0; i < n; i++) {
if (mask & (1 << i)) {
cout << i << " ";
}
}
cout << "}\n";
}
}
// 枚举给定集合 S 的所有非空子集
void enumerateSubsetsOf(int S) {
for (int sub = S; sub > 0; sub = (sub - 1) & S) {
// 处理子集 sub
// 技巧：(sub-1) & S 得到 S 的"下一个更小"子集
// 摊还 O(1) 步枚举 S 的全部 2^|S| 个子集
}
}
// 经典应用：状压 DP
// dp[mask] = 访问 mask 所表示的城市集合所需的最小代价
// dp[0] = 0（初始：没有访问任何城市）
// dp[mask | (1 << v)] = min(dp[mask | (1 << v)], dp[mask] + cost[last][v])
排列数：P(n, k) = n! / (n-k)! — 从 n 个中有序选 k 个
组合数：C(n, k) = n! / (k! × (n-k)!) — 从 n 个中无序选 k 个
📄
// 解答：带模运算的组合数学
// 假设已调用 E.1.3 中的 precompute()
// C(n, k) = n! / (k! * (n-k)!)
ll combination(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}
// P(n, k) = n! / (n-k)!
ll permutation(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * inv_fact[n-k] % MOD;
}
// 隔板法（星与条）：将 n 个相同球放入 k 个不同盒的方案数
// = C(n + k - 1, k - 1)
ll starsAndBars(int n, int k) {
return combination(n + k - 1, k - 1);
}
当 n 较小（n ≤ 2000）时，帕斯卡三角更简洁：
📄 当 n 较小（n ≤ 2000）时，帕斯卡三角更简洁：
// 解答：帕斯卡三角 DP — O(n^2) 预处理
const int MAXN = 2005;
ll C[MAXN][MAXN];
void buildPascal() {
for (int i = 0; i < MAXN; i++) {
C[i][0] = C[i][i] = 1;
for (int j = 1; j < i; j++) {
C[i][j] = (C[i-1][j-1] + C[i-1][j]) % MOD;
}
}
}
// 之后 C[n][k] 即为 0 <= k <= n < MAXN 时的组合数
// 完全避免了模逆元——当 MOD 可能不是素数时特别有用
帕斯卡恒等式： C(n, k) = C(n-1, k-1) + C(n-1, k)
含义："从 n 个中选 k 个" = "包含第 n 个元素，从 n-1 个中选 k-1 个" + "不包含第 n 个元素，从 n-1 个中选 k 个"。
📄 查看代码：常用组合恒等式
// 竞赛中常用的恒等式：
// 曲棍球恒等式：sum_{k=0}^{n} C(r+k, k) = C(n+r+1, n)
// 用途：二维前缀和、多项式求值
// 范德蒙德恒等式：sum_k C(m,k)*C(n,r-k) = C(m+n, r)
// 用途：涉及两组元素的计数问题
// 容斥原理：
// |A ∪ B| = |A| + |B| - |A ∩ B|
// |A ∪ B ∪ C| = |A| + |B| + |C| - |A∩B| - |A∩C| - |B∩C| + |A∩B∩C|
// 推广到 n 个集合时有 2^n 项（或用位掩码枚举）
1 + 1/2 + 1/3 + ... + 1/N ≈ ln(N) ≈ 0.693 × log₂(N)
这解释了为何埃筛运行时间为 O(N log log N)：
总工作量 = N/2 + N/3 + N/5 + N/7 + ...（对每个质数 p，标记 N/p 个倍数）
对所有质数求和 ≈ N × ln(ln(N))
以及为何树状数组操作是 O(log N)：lowbit 操作每次前进 1、2、4...位。
表达式 近似值 含义
log₂(10⁵) ≈ 17 10⁵ 个元素的 BST/线段树深度 log₂(10⁹) ≈ 30 在 10⁹ 范围内的二分查找步数 √(10⁶) = 1000 N ≤ 10⁶ 时试除法的上界 2²⁰ ≈ 10⁶ 状压 DP 上限（20 个元素） 20! ≈ 2.4 × 10¹⁸ 勉强放进 long long 13! ≈ 6 × 10⁹ 略超 int 上限
时间限制 安全操作数上限
1 秒 ~10⁸ 次简单操作 2 秒 ~2 × 10⁸ 3 秒 ~3 × 10⁸
据此可以估算算法是否够快：
N = 10⁵，O(N log N) → ~1.7 × 10⁶ 次操作 → 足够快
N = 10⁵，O(N²) → 10¹⁰ 次操作 → 太慢
N = 10⁵，O(N√N) → ~3 × 10⁷ 次操作 → 边界情况 （2 秒通常没问题）
以下是整合了本附录所有模板的单文件版本：
📄 以下是整合了本附录所有模板的单文件版本：
// 解答：竞赛编程完整数学模板
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
// ═══════════════════════════════════════════════
// 模运算
// ═══════════════════════════════════════════════
const ll MOD = 1e9 + 7;
ll power(ll base, ll exp, ll mod = MOD) {
ll result = 1;
base %= mod;
while (exp > 0) {
if (exp & 1) result = result * base % mod;
base = base * base % mod;
exp >>= 1;
}
return result;
}
ll modInverse(ll a, ll mod = MOD) {
return power(a, mod - 2, mod);
}
// ═══════════════════════════════════════════════
// 阶乘（预处理至 MAXN）
// ═══════════════════════════════════════════════
const int MAXN = 1000005;
ll fact[MAXN], inv_fact[MAXN];
void precomputeFactorials() {
fact[0] = 1;
for (int i = 1; i < MAXN; i++) fact[i] = fact[i-1] * i % MOD;
inv_fact[MAXN-1] = modInverse(fact[MAXN-1]);
for (int i = MAXN-2; i >= 0; i--) inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}
ll C(int n, int k) {
if (k < 0 || k > n) return 0;
return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}
// ═══════════════════════════════════════════════
// GCD / LCM
// ═══════════════════════════════════════════════
ll gcd(ll a, ll b) { return b == 0 ? a : gcd(b, a % b); }
ll lcm(ll a, ll b) { return a / gcd(a, b) * b; }
// ═══════════════════════════════════════════════
// 质数筛
// ═══════════════════════════════════════════════
const int MAXP = 1000005;
bool notPrime[MAXP];
vector<int> primes;
void sieve(int n = MAXP - 1) {
notPrime[0] = notPrime[1] = true;
for (int i = 2; i <= n; i++) {
if (!notPrime[i]) {
primes.push_back(i);
for (long long j = (long long)i*i; j <= n; j += i)
notPrime[j] = true;
}
}
}
bool isPrime(int n) { return n >= 2 && !notPrime[n]; }
// ═══════════════════════════════════════════════
// 位运算技巧
// ═══════════════════════════════════════════════
bool isOdd(int n) { return n & 1; }
bool isPow2(int n) { return n > 0 && !(n & (n-1)); }
int lowbit(int n) { return n & (-n); }
int popcount(int n) { return __builtin_popcount(n); }
int ctz(int n) { return __builtin_ctz(n); } // 尾部零个数
// ═══════════════════════════════════════════════
// 扩展 GCD
// ═══════════════════════════════════════════════
ll extgcd(ll a, ll b, ll &x, ll &y) {
if (!b) { x = 1; y = 0; return a; }
ll x1, y1, g = extgcd(b, a%b, x1, y1);
x = y1; y = x1 - a/b * y1;
return g;
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
precomputeFactorials();
sieve();
// 测试：C(10, 3) = 120
cout << C(10, 3) << "\n";
// 测试：2^100 mod (10^9+7)
cout << power(2, 100) << "\n";
// 测试：输出前 10 个质数
for (int i = 0; i < 10; i++) cout << primes[i] << " ";
cout << "\n";
return 0;
}
除数 规则
2 末位为偶数 3 各位数字之和能被 3 整除 4 末两位组成的数能被 4 整除 5 末位为 0 或 5 9 各位数字之和能被 9 整除 10 末位为 0 11 各位数字的交替和能被 11 整除
// 安全的整数平方根（避免浮点误差）
ll isqrt(ll n) {
ll x = sqrtl(n); // 浮点近似值
while (x * x > n) x--; // 若偏大则向下修正
while ((x+1) * (x+1) <= n) x++; // 若偏小则向上修正
return x;
}
// 正整数的向上取整除法：ceil(a/b)
ll ceilDiv(ll a, ll b) {
return (a + b - 1) / b;
// 等价写法：(a - 1) / b + 1（a > 0 时相同）
}
Q1：什么时候应该用 long long？
A：当数值可能超过 2 × 10⁹（大约是 int 的上限）时。典型场景：① 两个大 int 相乘（10⁹ × 10⁹ = 10¹⁸）；② 累加路径权重（N 条边，每条权重最大 10⁶，合计最大 10¹¹）；③ 阶乘/组合数（即使取模，中间计算也用 long long）。经验法则：竞赛代码中只要有乘法，就用 long long。
Q2：为什么用 10⁹ + 7 而非 10⁹？
A：10⁹ 不是素数（= 2⁹ × 5⁹），无法用费马小定理求模逆元。10⁹ + 7 = 1,000,000,007 是素数，且 (10⁹ + 7)² < 2⁶³（long long 的上限），因此取模后的两数相乘不会溢出 long long。
Q3：快速幂中的位运算技巧是怎么工作的？
A：将指数 n 写成二进制：n = b_k × 2^k + ... + b_1 × 2 + b_0。那么 a^n = a^(b_k × 2^k) × ... × a^(b_1 × 2) × a^b_0。每次循环将底数平方（代表 a 的 2^k 次幂），当前位为 1 时乘入结果。只需 log₂(n) 次乘法。
Q4：埃筛的内层循环为什么从 i×i 开始？
A：i 的倍数 2i, 3i, ..., (i-1)i 已被更小的质数 2, 3, ..., i-1 标记过。例如，6 = 2×3 已被 2 标记；7×5=35 已被 5 标记。从 i×i 开始可以避免冗余，优化常数因子。
Q5：为什么 n & (n-1) 能检测 n 是否为 2 的幂次？
A：2 的幂次在二进制中只有一个 1 位（如 8 = 1000）。减 1 会把最低的 1 位变为 0，并把其下所有 0 位翻转为 1（如 7 = 0111）。因此 n & (n-1) 清除了最低 1 位。若 n 是 2 的幂次（只有一个 1 位），结果为 0；否则不为 0。
附录 E 结束 — 另请参阅：算法模板库 | 竞赛编程技巧
