InoueMoby's Blog

前言

“从 10 个人里选 3 个人组队，有多少种选法？“——你在高中数学课上学过： $\binom{10}{3} = \frac{10!}{3! \times 7!} = 120$ 。

但在算法竞赛里，这道题往往是这样的：“从 $10^6$ 个人里选 $5 \times 10^5$ 个人组队，答案对 $10^9+7$ 或 $998244353$ 取模。“直接算 $10^6!$ ？那是一个约 $5.5 \times 10^6$ 位的数，存都存不下。而除法在模意义下又不能直接做——需要逆元。

上一篇 02-04 快速幂与逆元里预处理了阶乘和逆阶乘，现在正好用上。这篇文章覆盖从 $\binom{n}{k}$ 到 $O(1)$ 查询组合数的全部方法。

问题的本质

排列与组合

排列 $P(n, k)$ ：从 $n$ 个不同元素中有序选 $k$ 个。 $P(n,k) = \frac{n!}{(n-k)!}$ 。

组合 $C(n, k) = \binom{n}{k}$ ：从 $n$ 个不同元素中无序选 $k$ 个。 $\binom{n}{k} = \frac{n!}{k!(n-k)!}$ 。

关系： $P(n,k) = k! \times \binom{n}{k}$ （组合乘上 $k$ 个的排列数 = 排列）。

核心公式

$\binom{n}{k}$ 的几个常用性质：

性质	公式	直觉
对称性	$\binom{n}{k} = \binom{n}{n-k}$	选 $k$ 个 = 不选 $n-k$ 个
递推	$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}$	杨辉三角
求和	$\sum_{k=0}^{n}\binom{n}{k} = 2^n$	每个元素选或不选

理论 + 代码

预处理阶乘 + 逆阶乘（ $O(N)$ 预处理， $O(1)$ 查询）

在 02-04 里已经讲过。回顾一遍：

\binom{n}{k} = \frac{n!}{k! \cdot (n-k)!} = n! \cdot (k!)^{-1} \cdot ((n-k)!)^{-1}

预处理 fact[i] = i! mod p 和 inv_fact[i] = (i!)^{-1} mod p，然后每次查询只需三次查表加两次模乘。

const long long MOD = 1e9 + 7;
const int MAXN = 1000006;
long long fact[MAXN], inv_fact[MAXN];

long long qpow(long long a, long long n) {
    long long res = 1; a %= MOD;
    while (n > 0) {
        if (n & 1) res = res * a % MOD;
        a = a * a % MOD; n >>= 1;
    }
    return res;
}

void init() {
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)       // ① 阶乘：fact[i] = i × (i-1)!
        fact[i] = fact[i-1] * i % MOD;
    inv_fact[MAXN - 1] = qpow(fact[MAXN - 1], MOD - 2);  // ② (N!)^{-1}
    for (int i = MAXN - 2; i >= 0; i--)  // ③ 倒推
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;        // ④ 边界：非法输入返回 0
    return fact[n] * inv_fact[k] % MOD * inv_fact[n-k] % MOD;
    // ⑤ n! × (k!)^{-1} × ((n-k)!)^{-1}
}

③ 倒推原理： $(k!)^{-1} = ((k+1)!)^{-1} \times (k+1)$ 。因为 $(k+1)! = (k+1) \times k!$ ，所以 $k! = (k+1)! / (k+1)$ ，逆元 $(k!)^{-1} = (k+1) \times ((k+1)!)^{-1}$ 。
⑤ 两次 * ... % MOD。从左到右算：fact[n] * inv_fact[k] 结果取模，再乘 inv_fact[n-k] 取模。中间值最大 $(10^9)^2 = 10^{18}$ ，long long 没问题。

排列数 $P(n, k)$

P(n, k) = \frac{n!}{(n-k)!} = n! \times ((n-k)!)^{-1}

long long P(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fact[n] * inv_fact[n - k] % MOD;
}

只需要一个逆阶乘，比组合数还简单。

例题

例题 1：M&A 021 — Combination Easy（★1）

题目：给定 $n$ 和 $r$ ，求 $C(n, r) = \binom{n}{r}$ 。

数据范围： $1 \le r \le n \le 20$

—— AtCoder M&A 021

思路： $n \le 20$ ，直接用公式 $C(n,r) = n! / (r!(n-r)!)$ 不会溢出（ $20! \approx 2.4 \times 10^{18}$ 刚好在 long long 边缘，但先乘后除可以避免）。

代码：

#include <cstdio>
using namespace std;

int main() {
    int n, r;
    scanf("%d%d", &n, &r);

    // ① C(n, r) = n×(n-1)×...×(n-r+1) / (1×2×...×r)
    long long num = 1, den = 1;
    for (int i = 0; i < r; i++) {
        num *= (n - i);    // ② 分子：n, n-1, ..., n-r+1
        den *= (i + 1);    // ③ 分母：1, 2, ..., r
    }
    printf("%lld\n", num / den);
}

逐行解析：

②③ 同时乘分子和分母，避免单独算阶乘溢出。先乘后除，因为 $C(n,r)$ 一定是整数，所以 num 一定能被 den 整除。

例题 2：M&A 051 — Combination Hard（★2）

题目：从格子 $(0,0)$ 出发，每次向右或向上走一步。到达 $(X, Y)$ 有多少种走法？答案对 $10^9+7$ 取模。

数据范围： $1 \le X, Y \le 10^5$

—— AtCoder M&A 051

思路：从 $(0,0)$ 到 $(X,Y)$ 需要走 $X+Y$ 步，其中选 $X$ 步向右（其余向上）。方案数 = $C(X+Y, X)$ 。

$X+Y$ 最大 $2 \times 10^5$ ，用预计算阶乘 + 逆元：

$C(n, r) = \frac{n!}{r!(n-r)!} = n! \times (r!)^{-1} \times ((n-r)!)^{-1} \bmod p$

代码：

#include <cstdio>
using namespace std;

const long long MOD = 1000000007;
const int MAXN = 200010;
long long fact[MAXN], inv_fact[MAXN];

long long power(long long base, long long exp) {
    long long ans = 1;
    while (exp > 0) {
        if (exp & 1) ans = ans * base % MOD;
        base = base * base % MOD;
        exp >>= 1;
    }
    return ans;
}

int main() {
    // ① 预计算阶乘和阶乘逆元
    fact[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fact[i] = fact[i-1] * i % MOD;
    inv_fact[MAXN-1] = power(fact[MAXN-1], MOD - 2);  // ② 费马小定理求逆
    for (int i = MAXN - 2; i >= 0; i--)
        inv_fact[i] = inv_fact[i+1] * (i+1) % MOD;    // ③ 递推：1/i! = 1/(i+1)! × (i+1)

    int X, Y;
    scanf("%d%d", &X, &Y);
    int n = X + Y;
    // ④ C(n, X) = n! / (X! × Y!)
    printf("%lld\n", fact[n] * inv_fact[X] % MOD * inv_fact[Y] % MOD);
}

逐行解析：

② $inv\_fact[MAXN-1] = (fact[MAXN-1])^{-1} = (fact[MAXN-1])^{p-2} \bmod p$ （费马小定理）。
③ 从大往小递推： $(i!)^{-1} = ((i+1)!)^{-1} \times (i+1)$ ，因为 $i! \times (i+1) = (i+1)!$ 。

例题 3：Tessoku Book — A30 Combination

题目：求 $C(n, r) \bmod (10^9+7)$ 。

数据范围： $1 \le r \le n \le 10^5$

—— AtCoder Tessoku Book A30

思路：和例题 2 一样的预计算方法。作为独立练习。

代码：（同例题 2 的预计算部分，略）

例题 4：Tessoku Book — A05 Three Cards

题目：从 $1$ 到 $N$ 的整数中选 3 个不同的数，使它们的和恰好为 $K$ 。有多少种选法？

数据范围： $3 \le N \le 3000$ ， $3 \le K \le 9000$

—— AtCoder Tessoku Book A05

思路：三重循环 $O(N^3) = 2.7 \times 10^{10}$ ，太慢。但可以枚举前两个数 $a < b$ ，则 $c = K - a - b$ ，检查 $c > b$ 且 $c \le N$ 。

代码：

#include <cstdio>
using namespace std;

int main() {
    int N, K;
    scanf("%d%d", &N, &K);

    int cnt = 0;
    for (int a = 1; a <= N; a++) {       // ① 枚举最小的数
        for (int b = a + 1; b <= N; b++) { // ② 枚举中间的数
            int c = K - a - b;             // ③ 第三个数由 a+b+c=K 确定
            if (c > b && c <= N)           // ④ 保证 b < c 且 c ≤ N
                cnt++;
        }
    }
    printf("%d\n", cnt);
}

逐行解析：

①② $a < b$ 的约束通过 b = a + 1 保证。
③④ $c = K - a - b$ ，必须满足 $c > b$ （保证 $a < b < c$ ）和 $c \le N$ （不超出范围）。

例题 5：M&A 052 — Knight（★3）

题目：国际象棋棋盘上，马从原点 $(0,0)$ 出发，每步可以从 $(i,j)$ 移到 $(i+1,j+2)$ 或 $(i+2,j+1)$ 。到达 $(X,Y)$ 的路径数是多少？答案对 $10^9+7$ 取模。

数据范围： $1 \le X, Y \le 10^6$

—— AtCoder M&A 052

思路：设用了 $a$ 次 $(+1,+2)$ 移动和 $b$ 次 $(+2,+1)$ 移动，则：

$a + 2b = X, \quad 2a + b = Y$

解得 $a = (2Y-X)/3, b = (2X-Y)/3$ 。如果 $(2Y-X)$ 或 $(2X-Y)$ 不能被 3 整除，或者 $a<0, b<0$ ，答案为 0。

否则，总步数 $n = a + b$ ，从 $n$ 步中选 $a$ 步做第一种移动，方案数为 $C(n, a)$ 。用预处理阶乘+逆元 $O(1)$ 查询。

代码：

#include <cstdio>
using namespace std;
const int MOD = 1000000007;

// ① 预处理阶乘和逆元
long long fac[2000010], invfac[2000010];

long long power(long long base, long long exp) {
    long long ans = 1;
    while (exp > 0) {
        if (exp % 2 == 1) ans = ans * base % MOD;
        base = base * base % MOD;
        exp /= 2;
    }
    return ans;
}

long long C(int n, int r) {
    if (r < 0 || r > n) return 0;
    return fac[n] * invfac[r] % MOD * invfac[n-r] % MOD;  // ② C(n,r) = n!/(r!(n-r)!)
}

int main() {
    int X, Y;
    scanf("%d%d", &X, &Y);

    // ③ 检查是否有解
    int a_num = 2*Y - X, b_num = 2*X - Y;
    if (a_num < 0 || b_num < 0 || a_num % 3 != 0 || b_num % 3 != 0) {
        printf("0\n");
        return 0;
    }
    int a = a_num / 3, b = b_num / 3;
    int n = a + b;

    // ④ 预处理阶乘
    fac[0] = 1;
    for (int i = 1; i <= n; i++)
        fac[i] = fac[i-1] * i % MOD;
    invfac[n] = power(fac[n], MOD-2);  // ⑤ 费马小定理求逆元
    for (int i = n-1; i >= 0; i--)
        invfac[i] = invfac[i+1] * (i+1) % MOD;

    printf("%lld\n", C(n, a));  // ⑥ 答案 = C(a+b, a)
}

逐行解析：

③ 列方程 $a+2b=X, 2a+b=Y$ ，解出 $a=(2Y-X)/3, b=(2X-Y)/3$ 。必须是非负整数才有解。
④⑤ 预处理 $0!$ 到 $n!$ 以及它们的逆元。用费马小定理： $n!^{-1} \equiv (n!)^{p-2} \pmod{p}$ 。
⑥ $C(a+b, a)$ 表示从 $a+b$ 步中选 $a$ 步做第一种移动，这就是路径总数。
验证： $(X,Y)=(3,3)$ ， $a=1, b=1, n=2, C(2,1)=2$ 。路径 $(0,0)\to(1,2)\to(3,3)$ 和 $(0,0)\to(2,1)\to(3,3)$ 。✓

参考文献

理论讲义 — AtCoder Algorithm Lectures

合同式の基礎（難易度 1）

教材讲解 — 競技プログラミングの鉄則第 5 章

5.5 B30 Combination 2（组合数+快速幂求逆元解说）

基础练习 — アルゴリズムと数学演習問題集

系统练习 — 競技プログラミングの鉄則

系列索引

第零章基础工具

第一章搜索技术

第二章数学基础

第三章数据结构

第四章图论

第五章动态规划

第六章贪心

第七章字符串

第八章进阶

组合计数

排列、组合与模意义下的C(n,k)预处理

前言

问题的本质

排列与组合

核心公式

理论 + 代码

预处理阶乘 + 逆阶乘（ $O(N)$ 预处理， $O(1)$ 查询）

排列数 $P(n, k)$

例题

例题 1：M&A 021 — Combination Easy（★1）

例题 2：M&A 051 — Combination Hard（★2）

例题 3：Tessoku Book — A30 Combination

例题 4：Tessoku Book — A05 Three Cards

例题 5：M&A 052 — Knight（★3）

参考文献

系列索引

组合计数

组合计数

排列、组合与模意义下的C(n,k)预处理

前言

问题的本质

排列与组合

核心公式

理论 + 代码

预处理阶乘 + 逆阶乘（O(N)O(N)O(N) 预处理，O(1)O(1)O(1) 查询）

排列数 P(n,k)P(n, k)P(n,k)

例题

例题 1：M&A 021 — Combination Easy（★1）

例题 2：M&A 051 — Combination Hard（★2）

例题 3：Tessoku Book — A30 Combination

例题 4：Tessoku Book — A05 Three Cards

例题 5：M&A 052 — Knight（★3）

参考文献

系列索引

组合计数

预处理阶乘 + 逆阶乘（ $O(N)$ 预处理， $O(1)$ 查询）

排列数 $P(n, k)$