第 8.3 章：组合数学

8.3.0 从一道题出发：安排奶牛进栏

先看一道典型的 Gold 风格题目：

🌾 题目：奶牛分栏 农夫 John 有 N 头两两不同的奶牛和 K 个不同的牛栏（K < N）。他要从中选出 K 头奶牛，分别关进 K 个牛栏（每栏恰好一头）。 问：有多少种安排方案？答案对 10⁹ + 7 取模。

输入样例：

N = 10, K = 3

先试试你会的方法

思路 1：暴力枚举？ 从 10 头中选 3 头有 C(10,3) = 120 种选法，每种里 3 头奶牛分到 3 个栏又有 3! = 6 种安排——总共 720。N 再大一点呢？C(100, 50) 有 30 位数字，枚举到宇宙热寂也数不完。

思路 2：找到「计数公式」？ 「选 K 头 + 有序安排」恰好是排列数 P(N, K) = N!/(N−K)!。问题转化为：如何计算一个巨大的阶乘表达式对素数取模的值？除法在模意义下怎么做？

拆解这道题需要回答的问题

1. 计数的基本原理是什么？→ 加法原理与乘法原理
2. 模意义下的除法怎么做？→ 模逆元（第 8.1 章）
3. C(n, k) 有几种高效算法？→ 杨辉三角 / 单次逆元 / 阶乘预处理
4. 「n 个相同球放 k 个盒」怎么数？→ 隔板法
5. 「至少满足一个条件」怎么数？→ 容斥原理
6. USACO Gold 怎么包装这些？→ 8.3.6 节的题型模式

学习目标：

• 区分排列与组合，正确选用加法/乘法原理
• 实现三种 C(n,k) mod p 算法并知道各自适用场景
• 用隔板法解决「相同物品分组」计数
• 用容斥原理处理「至少/至多」约束

🔗 前置知识： 模运算、快速幂与模逆元已在第 8.1 章讲过，本章直接使用 power(a, MOD-2) 求逆元，不再重复推导。

8.3.1 加法/乘法原理与排列组合

一切计数都建立在两条公理上：

• 加法原理： 做一件事有若干互斥的途径，方案数 = 各途径方案数之和。（去 A 餐厅有 3 种路线，去 B 餐厅有 4 种，选一家 → 3 + 4 = 7 种）
• 乘法原理： 做一件事分若干相继的步骤，方案数 = 各步骤方案数之积。（上衣 3 件、裤子 4 条 → 3 × 4 = 12 套搭配）

排列与组合

关系：P(n, k) = C(n, k) × k! ——「先无序选，再排顺序」。

开篇题的答案就是 P(10, 3) = 10! / 7! = 720，与暴力枚举一致 ✓。

基本性质（后面反复用）：

• C(n, 0) = C(n, n) = 1
• 对称性： C(n, k) = C(n, n−k)
• 吸收律： C(n, k) = (n/k) · C(n−1, k−1)
• 帕斯卡递推： C(n, k) = C(n−1, k−1) + C(n−1, k)（「含不含某个特定元素」二分）

8.3.2 C(n, k) 的三种求法

方法一：杨辉三角 DP（无除法，n, k ≤ 2000）

用帕斯卡递推逐行填表。不需要逆元——连模数不是素数都能用——但 O(n²) 的时空限制了规模。

const long long MOD = 1e9 + 7;
long long dp[2001][2001];

void precompute_pascal(int maxn) {
    for (int i = 0; i <= maxn; i++) {
        dp[i][0] = 1;
        for (int j = 1; j <= i; j++)
            dp[i][j] = (dp[i-1][j-1] + dp[i-1][j]) % MOD;
    }
}
// 查询：C(n, k) = dp[n][k]

方法二：单次逆元法（n 任意大，k ≤ 10⁶）

把公式 C(n, k) = n·(n−1)···(n−k+1) / k! 拆成「k 项分子连乘 × (k!)⁻¹」：

typedef long long ll;
const ll MOD = 1e9 + 7;

ll power(ll a, ll n, ll p) {          // 快速幂 — 见第 8.1 章
    a %= p;
    ll result = 1;
    while (n > 0) {
        if (n & 1) result = result * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return result;
}

// 单次计算 C(n, k) mod p — O(k log p)
ll C_single(ll n, ll k) {
    if (k < 0 || k > n) return 0;
    k = min(k, n - k);                 // 用对称性减少循环次数
    ll num = 1, den = 1;
    for (ll i = 0; i < k; i++) {
        num = num * ((n - i) % MOD) % MOD;
        den = den * ((i + 1) % MOD) % MOD;
    }
    return num * power(den, MOD - 2, MOD) % MOD;
}
// C_single(10, 3) = 120 ✓

适用：n 可以高达 10¹⁸（n 只出现在分子乘积里，对 MOD 取模即可），但要求 k 较小。

方法三：预处理阶乘 + 逆元（O(N) 预处理，O(1) 查询）——竞赛标配

当查询次数很多（如 T ≤ 10⁶ 次，n ≤ 10⁶）时，先把阶乘表和逆阶乘表建好：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 1e6 + 5;
const ll MOD = 1e9 + 7;

ll fact[MAXN], inv_fact[MAXN];

ll power(ll a, ll n, ll p) {           // 快速幂 — 见第 8.1 章
    a %= p;
    ll result = 1;
    while (n > 0) {
        if (n & 1) result = result * a % p;
        a = a * a % p;
        n >>= 1;
    }
    return result;
}

// O(N) 预处理 fact[] 与 inv_fact[]
void precompute_factorials(int n) {
    fact[0] = 1;
    for (int i = 1; i <= n; i++)
        fact[i] = fact[i-1] * i % MOD;

    // 关键技巧：先花一次 O(log p) 求出 inv_fact[n]，
    // 再用 inv_fact[i] = inv_fact[i+1] * (i+1) 倒序推出全部 —— 省掉 N 次快速幂
    inv_fact[n] = power(fact[n], MOD - 2, MOD);   // 费马小定理（第 8.1 章）
    for (int i = n - 1; i >= 0; i--)
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}

// O(1) 查询 C(n, k) mod p
ll C(int n, int k) {
    if (k < 0 || k > n || n < 0) return 0;   // 边界保护必须有！
    return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
}

// 顺便可得排列数 P(n, k) = n! / (n-k)!
ll P(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[n-k] % MOD;
}

int main() {
    precompute_factorials(1e6);
    cout << C(10, 3) << "\n";    // 120
    cout << C(100, 50) << "\n";  // 538992043（mod 1e9+7）
    cout << P(10, 3) << "\n";    // 720 —— 开篇题的答案
    return 0;
}

倒序递推 inv_fact 的原理：1/i! = 1/(i+1)! × (i+1)。这样 N 次逆元只花 一次快速幂的代价。

三种方法对比

💡 进阶（Platinum）： 当 n 极大（10¹²+）而素数模数 p 较小（< 10⁶）时，用 Lucas 定理：C(n,k) mod p = C(n mod p, k mod p) × C(n/p, k/p) mod p，递归分解。

8.3.3 常用公式与恒等式（大表）

计数公式表

恒等式表

卡特兰数在 USACO 中出现频率出人意料地高（括号序列、出栈序列、多边形三角剖分、避开对角线的网格路径）：

// 卡特兰数 Cat_n = C(2n, n) / (n+1)  —— 依赖 8.3.2 的 C() 与预处理
ll catalan(int n) {
    return C(2*n, n) % MOD * power(n + 1, MOD - 2, MOD) % MOD;
}
// Cat_0=1, Cat_1=1, Cat_2=2, Cat_3=5, Cat_4=14, Cat_5=42, ...

8.3.4 隔板法与鸽巢原理

隔板法（Stars and Bars）

n 个相同的球放进 k 个不同的盒子，盒子可空，有多少种放法？

把球排成一行（n 个 ★），在球与球之间及两端共 n+k−1 个位置中选 k−1 个插入隔板 ▏，每相邻两隔板间的球数即一个盒子的球数：

★ ★ ▏ ★ ★ ★ ▏ ▏ ★   →  盒1=2, 盒2=3, 盒3=0, 盒4=1

「每盒至少一个」的版本： 先每盒垫 1 个球（用掉 k 个），剩下 n−k 个随便放 → C(n−1, k−1)。也可以直接理解为隔板必须插在球与球之间、不能相邻。

例： 把 7 份相同的草料分给 3 头奶牛，允许有奶牛分不到 → C(9, 2) = 36 种。

鸽巢原理

把 n+1 个物品放进 n 个盒子，必有某个盒子里至少有 2 个物品。

看似显然，却是一类「证明存在性」题的钥匙。竞赛中的典型用法：

• 任意 13 个人中，必有两人出生月份相同（12 个「盒子」）。
• 从 1..2n 中任取 n+1 个数，必有一个整除另一个（按「奇数部分」装盒：每个数写成 2^a·q，q 为奇数，只有 n 个盒子）。
• 区间和问题：n 个前缀和 mod n，要么有 0 要么有两个相同 → 必存在连续区间和被 n 整除。

鸽巢只保证存在，不告诉你是哪个——它用于证明和构造性下界，不用于计数。

8.3.5 容斥原理

从两个集合到三个集合

计数「至少属于一个集合」的元素时，直接相加会重复，需要交替减加：

|A ∪ B|       = |A| + |B| − |A ∩ B|
|A ∪ B ∪ C|   = |A| + |B| + |C|
                − |A∩B| − |A∩C| − |B∩C|
                + |A∩B∩C|

三个集合的直观解释：加单集时，恰好属于两个集合的元素被数了 2 次（多 1 次，减去二元交补回）；三集合交的元素被数了 3 次、又被减了 3 次（净 0 次，加回三元交）。

推广到 n 个集合：

子集数量为 2ⁿ，当 n 较小时用位掩码枚举所有交集。

经典例题 1：整除计数

1 到 N 中有多少个数能被 a 或 b 整除？

• |被 a 整除| = ⌊N/a⌋，|被 b 整除| = ⌊N/b⌋，|同时被整除| = ⌊N/lcm(a,b)⌋
• 答案 = ⌊N/a⌋ + ⌊N/b⌋ − ⌊N/lcm(a,b)⌋

手算验证： N = 20, a = 3, b = 5。⌊20/3⌋ + ⌊20/5⌋ − ⌊20/15⌋ = 6 + 4 − 1 = 9。枚举：3,5,6,9,10,12,15,18,20——正好 9 个 ✓。

// 1..n 中能被 k 个给定数 {a1..ak} 之一整除的个数（k ≤ 20，位掩码容斥）
long long count_divisible(long long n, vector<long long>& a) {
    int k = a.size();
    long long ans = 0;
    for (int mask = 1; mask < (1 << k); mask++) {
        long long lcm = 1;
        for (int i = 0; i < k; i++)
            if (mask & (1 << i)) {
                lcm = lcm / __gcd(lcm, a[i]) * a[i];
                if (lcm > n) break;         // 提前剪枝，防溢出
            }
        if (lcm > n) continue;
        if (__builtin_popcount(mask) % 2 == 1) ans += n / lcm;  // 奇数加
        else                                       ans -= n / lcm;  // 偶数减
    }
    return ans;
}

经典例题 2：「每个值都出现」的序列计数

统计长度为 N 的序列（元素取 1..M），使得 1..K 中每个值至少出现一次。N, M ≤ 10⁶，K ≤ M。

直接数「每个都出现」很难，反过来对「缺失的值」容斥：

答案 = Σ_{j=0}^{K} (−1)ʲ × C(K, j) × (M−j)ᴺ

• 选 j 个值禁止出现：C(K, j) 种选法；
• 剩下 M−j 个值随便填 N 个位置：(M−j)ᴺ 种；
• 奇偶交替加减，恰好把「缺 1 个」「缺 2 个」……的多算全部抵消。

// 依赖 8.3.2 的 C() 与 power()
long long count_surjective(int n, int m, int k) {
    long long ans = 0;
    for (int j = 0; j <= k; j++) {
        long long term = C(k, j) * power(m - j, n, MOD) % MOD;
        if (j % 2 == 0) ans = (ans + term) % MOD;
        else            ans = (ans - term + MOD) % MOD;   // 加 MOD 防负！
    }
    return ans;
}

经典例题 3：错排（Derangement）

n 个人交换帽子，每人都不拿回自己帽子的方案数 Dₙ。

对「至少一人拿回自己的帽子」容斥，得到：

更实用的是递推：Dₙ = (n−1)(Dₙ₋₁ + Dₙ₋₂)，D₁ = 0，D₂ = 1。验证：D₃ = 2×(0+1) = 2（3 顶帽子全错位确实只有 2 种）。

8.3.6 USACO Gold 数学题型模式

模式 1：用 DP 计数

「统计长度为 N 的合法序列数，每个元素从 1..M 选取并满足约束。」

当约束有复杂的相邻依赖（如「相邻元素不同」「前缀和限制」）时，封闭公式难找，建模为 DP：dp[i][状态] = 以某状态结尾的长度 i 序列数，转移用乘法原理，答案取模。组合数学提供公式，DP 提供状态设计——两者常常结合：先用 DP 建表，再用组合数求和（另见第 6.7 章计数 DP）。

模式 2：整除约束 + 容斥

「1 到 N 中有多少数至少能被 {a₁, ..., aₖ} 之一整除？」

容斥：Σ⌊N/aᵢ⌋ − Σ⌊N/lcm(aᵢ,aⱼ)⌋ + ...，位掩码枚举（k ≤ 20），见 8.3.5 例题 1。注意 lcm 会在 20 个数时爆 long long，需边乘边与 N 比较、及时剪枝。

// 基础积木：n 以内 m 的倍数个数
long long count_multiples(long long n, long long m) { return n / m; }

模式 3：隔板法（Stars and Bars）

「将 N 个相同物品分配到 K 个盒子，满足某些约束。」

无约束：C(N+K−1, K−1)。有「每盒至多 X 个」的约束：转换成「至少」再用容斥，或生成函数。识别信号：题面出现「相同的」「非负整数解」「恰好分完」。

模式 4：对称性 / Burnside 引理

「统计不同的项链/着色方案数（旋转或翻转等价的视为相同）。」

Burnside 引理：等价类数 = 每个群元素不动点数的平均值。对旋转群，旋转 d 步的不动点数为 K^gcd(n,d)（n 珠 K 色），于是：

项链数 = (1/n) × Σ_{d=0}^{n-1} K^gcd(n, d)

USACO Gold 中不常见但一出现就令人印象深刻；与第 8.2 章的欧拉 φ（Σ φ(d)·K^(n/d)/n 形式）联动。

⚠️ 常见错误

📋 章节小结

❓ 常见问题

Q：怎么判断一道题用组合公式还是 DP？ A：约束「漂亮」（无相邻依赖）且有封闭形式 → 组合公式；约束复杂纠缠 → DP。实际常常组合：DP 建表 + 组合数求和。

Q：USACO 中最常见的模数？ A：10⁹ + 7（素数），偶尔 998244353（素数，NTT 友好）。两者都能用费马小定理求逆元。

🔗 与后续章节的联系

• 第 8.1 章（数论基础）： 本章所有除法都靠那里的模逆元。
• 第 6.7 章（计数 DP）： 本章提供公式工具，该章提供状态设计思路。
• 第 8.2 章（筛法）： 「1..N 中与 k 互素的数」= 容斥（用 k 的质因子）+ 筛法分解——两章的组合拳。

🏋️ 练习题

🟢 基础

8.3-P1. 网格路径计数
统计从 (0,0) 走到 (n, m) 的路径数（每步向右或向上），n, m ≤ 10⁶，答案 mod 10⁹+7。

8.3-P2. 分草料
把 7 份相同的草料全部分给 3 头奶牛，每头至少 1 份，有多少种分法？先手算，再用 C() 验证。

🟡 中等

8.3-P3. 缺失值容斥
统计长度为 N=3、元素取自 {1..M=2}、且 K=2 个值都至少出现一次的序列数（mod 10⁹+7）。先手算，再用 count_surjective 验证。

8.3-P4. 至多容斥变体
1 到 1000 中，既不被 3 整除也不被 7 整除的数有多少个？

🔴 困难

8.3-P5. 合法括号序列
统计长度为 2n（n ≤ 10⁶）的合法括号序列个数，mod 10⁹+7。