「一本通 6.6 例 3」组合

形式化题目

给定 $T$ 组询问，每组给出三个正整数 $n, m, p$ （其中 $p$ 为质数，且满足 $1 \leqslant m \leqslant n \leqslant 10^9$ ， $m \leqslant 10^4$ ， $m < p < 10^9$ ）。求：

\binom{n}{m} \bmod p

正解

思路

当 $n \geqslant p$ 时，组合数 $\binom{n}{m} = \frac{n!}{m!(n-m)!}$ 的分子分母展开式中可能包含模数 $p$ 的倍数，直接求逆元会遇到分母与模数不互质的问题。对于模数 $p$ 为质数的场景，可使用 Lucas 定理进行转化。

Lucas 定理指出，对于任意非负整数 $n, m$ 与质数 $p$ ：

\binom{n}{m} \equiv \binom{n \bmod p}{m \bmod p} \times \binom{\lfloor n/p \rfloor}{\lfloor m/p \rfloor} \pmod p

从进制的角度来看，相当于将 $n$ 与 $m$ 表示为 $p$ 进制展开：

n = \sum_{i=0}^k a_i p^i,\quad m = \sum_{i=0}^k b_i p^i \quad (0 \leqslant a_i, b_i < p)

则原组合数在模

p

意义下等价于各位组合数的乘积：

\binom{n}{m} \equiv \prod_{i=0}^k \binom{a_i}{b_i} \pmod p

对于每一位的小组合数 $\binom{a_i}{b_i} \bmod p$ ：

若 $a_i < b_i$ ，则方案数为 $0$ ，整体答案直接为 $0$ ；
若 $a_i \geqslant b_i$ ，因为题设保证 $m \leqslant 10^4$ ，所以 $b_i \leqslant m \leqslant 10^4$ 的规模很小。我们可以直接将分子 $a_i \times (a_i - 1) \times \dots \times (a_i - b_i + 1)$ 与分母 $1 \times 2 \times \dots \times b_i$ 分别连乘取模。由于 $p > m \geqslant b_i$ 且 $p$ 为质数，分母中所有数与 $p$ 互质，利用费马小定理通过快速幂计算分母模 $p$ 的逆元 $\text{den}^{p-2} \bmod p$ 即可完成单项计算。

整体使用迭代循环提取 $p$ 进制位，逐步乘入总结果中。

代码

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#!/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-03-31 10:00
# update_at: 2026-03-31 10:00

import sys
from functools import reduce


def comb_small(n: int, m: int, p: int) -> int:
    """计算单步较小规模组合数 C(n, m) mod p，要求 n, m < p。"""
    if m < 0 or m > n:
        return 0
    m = min(m, n - m)
    # 分子 (n-m+1)*...*n，分母 1*...*m
    num = reduce(lambda a, b: a * b % p, range(n - m + 1, n + 1), 1)
    den = reduce(lambda a, b: a * b % p, range(1, m + 1), 1)
    return num * pow(den, p - 2, p) % p


def lucas(n: int, m: int, p: int) -> int:
    """根据 Lucas 定理计算 C(n, m) mod p，将 n, m 转为 p 进制逐位计算。"""
    ans = 1
    while n > 0 or m > 0:
        ans = ans * comb_small(n % p, m % p, p) % p
        n //= p
        m //= p
    return ans


def solve() -> None:
    data = iter(map(int, sys.stdin.buffer.read().split()))
    T = next(data)
    out = [str(lucas(next(data), 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/**
 * 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-06 00:35
 * update_at: 2026-10-06 00:35
 */
#include <cstdio>
using namespace std;

typedef long long ll;

// 快速幂：计算 base^exp mod mod，用于费马小定理求逆元
ll fast_pow(ll base, ll exp, ll mod) {
    ll res = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) res = res * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return res;
}

// 计算单步组合数 C(n, m) mod p，要求 n, m < p 且 p 为质数
ll comb_small(ll n, ll m, ll p) {
    if (m < 0 || m > n) return 0;
    if (m > n - m) m = n - m; // 取较小的一侧，减少连乘项数
    ll num = 1; // 分子 (n-m+1) * ... * n
    ll den = 1; // 分母 1 * ... * m
    for (ll i = 1; i <= m; i++) {
        num = num * ((n - m + i) % p) % p;
        den = den * (i % p) % p;
    }
    // 分母与 p 互质（p 为质数且 p > m），用费马小定理求逆元
    return num * fast_pow(den, p - 2, p) % p;
}

// Lucas 定理：把 n, m 按 p 进制逐位拆开，各位小组合数相乘
ll lucas(ll n, ll m, ll p) {
    ll ans = 1;
    while (n > 0 || m > 0) {
        ans = ans * comb_small(n % p, m % p, p) % p;
        if (ans == 0) return 0; // 某一位出现 C(a_i, b_i) = 0，整体即为 0
        n /= p;
        m /= p;
    }
    return ans;
}

int main() {
    ll T;
    scanf("%lld", &T);
    while (T--) {
        ll n, m, p;
        scanf("%lld %lld %lld", &n, &m, &p);
        printf("%lld\n", lucas(n, m, p));
    }
    return 0;
}

复杂度

时间复杂度：将 $n, m$ 转换为 $p$ 进制位需要 $O(\log_p n)$ 步。每一位计算小组合数时，连乘项数不超过 $m$ 项，求逆元耗时 $O(\log p)$ 。因此单组数据时间复杂度为 $O(m \log_p n + \log p)$ 。由于 $m \leqslant 10^4$ 且 $p > m$ ，在极限情况下运算量也非常小，总时间复杂度为 $O(T(m \log_p n + \log p))$ 。
空间复杂度：仅需存储常数个临时变量，辅助空间复杂度为 $O(1)$ 。

总结

当组合数 $\binom{n}{m}$ 中 $n$ 极大且模数 $p$ 为质数时，Lucas 定理提供了将大范围组合数降维到模数以内的标准桥梁。利用 $p$ 进制按位拆分，将大问题转化为若干小组合数的乘积，再结合逆元与快速幂即可高效求解。

「一本通 6.6 例 3」组合

目录

形式化题目

正解

思路

代码

复杂度

总结