「一本通 6.6 练习 5」Combination

形式化题目

$t$ 组询问，每组给出 $n, m$ ，求组合数 $\binom{n}{m} \bmod 10007$ 的值。

正解

思路

1. 模数是素数：Lucas 定理登场

模数 $p = 10007$ 是素数。当 $n$ 很大（本题 $n$ 可远超 $p$ ）而模数是小素数时，直接对阶乘取模求组合数会因 $n!$ 含因子 $p$ 而失效（逆元不存在）。此时用 Lucas 定理：

\binom{n}{m} \equiv \prod_{i} \binom{n_i}{m_i} \pmod p

其中 $n_i, m_i$ 是 $n, m$ 的 $p$ 进制展开各位数字。每个因子 $\binom{n_i}{m_i}$ 的上下参数都小于 $p$ ，可直接用预处理的阶乘 + 逆元在 $O(1)$ 求出；若某位 $m_i > n_i$ ，整个乘积为 $0$ 。

2. 小组合数的 O(1) 求法

预处理 $p$ 以内阶乘表 $F[i] = i! \bmod p$ 。对 $n, m < p$ ：

\binom{n}{m} \equiv F[n] \cdot (F[m] \cdot F[n-m])^{-1} \pmod p

分母的逆元用费马小定理： $x^{-1} \equiv x^{p-2} \pmod p$ ，Python 内置 pow(x, -1, p) 即可一步求出。

3. 实现要点

阶乘表只需 $p = 10007$ 项，一次预处理，所有询问共用；
Lucas 按 $p$ 进制逐位拆解：while n or m: 取 n%p, m%p 对应因子；n //= p; m //= p；
每组询问 $O(\log_p n)$ ，配合 $O(1)$ 的单因子查询，总复杂度极低。

代码

Python 版：

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-01 00:21
# update_at: 2026-10-01 00:21

import sys
from itertools import accumulate

MOD = 10007  # 题面模数，恰好是素数：Lucas 定理和费马小定理都能用

# FACT[i] = i! mod MOD（只用到 i < MOD），共 MOD 项；p 进制每一数位的组合数都查它
FACT = list(accumulate(range(1, MOD), lambda acc, i: acc * i % MOD, initial=1))


def small_comb(n: int, m: int) -> int:
    """p 进制单个数位上的 C(n, m) mod p（传入的 n, m 都已小于 p）。"""
    if m > n:
        return 0  # 这一位 m 已经超过 n，整个 Lucas 乘积因子为 0
    return FACT[n] * pow(FACT[m] * FACT[n - m], -1, MOD) % MOD  # 逆元当除法


def lucas(n: int, m: int) -> int:
    """Lucas 定理：C(n, m) ≡ ∏ C(n_i, m_i) (mod p)，n_i / m_i 是 p 进制各位数字。"""
    res = 1
    while n or m:
        res = res * small_comb(n % MOD, m % MOD) % MOD
        n //= MOD
        m //= MOD
    return res


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    t = next(data)  # 询问组数
    out = [str(lucas(next(data), next(data))) for _ in range(t)]
    print('\n'.join(out))


if __name__ == "__main__":
    solve()

C++ 版（同一算法）：

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-14 09:00
 * update_at: 2026-10-06 00:48
 */
#include <cstdio>

typedef long long ll;

const ll P = 10007; // 模数，是素数，Lucas 定理和费马小定理都依赖这一点
const int MAXP = 10007;

ll t, n, m;
ll f[MAXP]; // f[i] = i! mod P，只预处理 P 以内的阶乘

// 快速幂：a^b mod P
ll qpow(ll a, ll b) {
    ll res = 1;
    a %= P;
    while (b > 0) {
        if (b & 1) res = res * a % P;
        a = a * a % P;
        b >>= 1;
    }
    return res;
}

// 求 P 以内两个数的组合数 C(a, b) mod P，a、b 均小于 P
// 分母的逆元用费马小定理：x^(-1) = x^(P-2) mod P
ll small_comb(ll a, ll b) {
    if (b < 0 || b > a) return 0;
    return f[a] * qpow(f[b] * f[a - b] % P, P - 2) % P;
}

// Lucas 定理：把 C(n, m) mod P 按 P 进制拆成各位小组合数的乘积
// 若某一位 m 的数字大于 n 的数字，说明这一位上选不下，整个组合数为 0
ll lucas(ll n, ll m) {
    ll ans = 1;
    while (n > 0 || m > 0) {
        ans = ans * small_comb(n % P, m % P) % P;
        if (ans == 0) return 0; // 某位为 0，后面不用再算
        n /= P;
        m /= P;
    }
    return ans;
}

int main() {
    // 预处理阶乘表，所有询问共用
    f[0] = 1;
    for (int i = 1; i < P; i++) f[i] = f[i - 1] * i % P;

    scanf("%lld", &t);
    while (t--) {
        scanf("%lld %lld", &n, &m);
        printf("%lld\n", lucas(n, m));
    }
    return 0;
}

复杂度

时间复杂度：预处理 $O(p)$ ；每组询问 $O(\log_p n)$ ，总 $O(p + t \log_p n)$ 。
空间复杂度： $O(p)$ ，阶乘表共 $10007$ 项。

总结

「大 $n$ 小素数模」组合数的标准解法就是 Lucas 定理： $p$ 进制拆位，把大组合数化为若干小组合数的乘积。
费马小定理 + Python 的 pow(x, -1, p) 让模逆元实现只需一行。
预处理阶乘表是所有询问共享的固定成本，整个程序 IO 之外几乎全是查表。

「一本通 6.6 练习 5」Combination

目录

形式化题目

正解

思路

1. 模数是素数：Lucas 定理登场

2. 小组合数的 O(1) 求法

3. 实现要点

代码

复杂度

总结