AcWing 886. 求组合数 II

◎

本节目标

用阶乘和逆阶乘快速回答大范围组合数查询。

题意与约束

多组 a, b 的上界比 Pascal 表更大，需要输出 C(a,b) mod 1_000_000_007。

第一反应与瓶颈

Pascal 三角需要 O(N²) 空间和时间，N=100000 时不可用。逐查询计算阶乘又浪费了共享前缀。

数学关系与算法推导

把每个全排列的前 b 个位置视作选中的元素。一个固定的 b 元子集会被重复计数 b!(a-b)! 次：选中部分有 b! 种内部顺序，未选部分有 (a-b)! 种内部顺序。因此 a!=C(a,b)·b!·(a-b)!，也就是 C(a,b)=a!/(b!(a-b)!)。模运算不能直接做这两个除法；因为本题模数是质数且相关阶乘非零，可预处理 fact[i]=i!，再用费马小定理求 invFact[N]=fact[N]^(MOD-2)，从后向前递推 invFact[i-1]=invFact[i]·i。最终用 fact[a]·invFact[b]·invFact[a-b] 回答。

正确性依据

费马小定理保证非零阶乘在本题模数下有逆元。逆阶乘后推式恰好撤销一个因子，因此三个数组项的乘积等于阶乘公式中的分子乘分母逆元。

样例执行过程

C(100000,1)=100000，并且由对称性 C(100000,99999) 也为 100000，两个查询共享同一组预处理。

代码实现

C++

C++17

#include <algorithm>
#include <iostream>
#include <utility>
#include <vector>
using namespace std;

constexpr long long MOD = 1000000007;

long long modPower(long long base, long long exponent) {
    long long result = 1;
    while (exponent > 0) {
        if ((exponent & 1) != 0) {
            result = result * base % MOD;
        }
        base = base * base % MOD;
        exponent >>= 1;
    }
    return result;
}

vector<int> combinationQueriesFactorial(const vector<pair<int, int>>& queries) {
    int maximum = 0;
    for (const auto& [a, b] : queries) {
        maximum = max(maximum, a);
    }
    vector<long long> factorial(maximum + 1, 1);
    vector<long long> inverseFactorial(maximum + 1, 1);
    for (int value = 1; value <= maximum; value++) {
        factorial[value] = factorial[value - 1] * value % MOD;
    }
    if (maximum > 0) {
        inverseFactorial[maximum] = modPower(factorial[maximum], MOD - 2);
        for (int value = maximum; value > 0; value--) {
            inverseFactorial[value - 1] = inverseFactorial[value] * value % MOD;
        }
    }

    vector<int> answers;
    answers.reserve(queries.size());
    for (const auto& [a, b] : queries) {
        if (b < 0 || b > a) {
            answers.push_back(0);
        } else {
            answers.push_back(static_cast<int>(factorial[a] * inverseFactorial[b] % MOD * inverseFactorial[a - b] % MOD));
        }
    }
    return answers;
}

#ifndef ALGORITHM_TUTORIAL_NO_MAIN
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int count;
    cin >> count;
    vector<pair<int, int>> queries(count);
    for (auto& [a, b] : queries) {
        cin >> a >> b;
    }
    for (int answer : combinationQueriesFactorial(queries)) {
        cout << answer << '\n';
    }
    return 0;
}
#endif

Python

Python 3

import sys


MOD = 1_000_000_007


def mod_power(base: int, exponent: int) -> int:
    result = 1
    while exponent > 0:
        if exponent & 1:
            result = result * base % MOD
        base = base * base % MOD
        exponent >>= 1
    return result


def combination_queries_factorial(queries: list[tuple[int, int]]) -> list[int]:
    maximum = max((a for a, _ in queries), default=0)
    factorial = [1] * (maximum + 1)
    inverse_factorial = [1] * (maximum + 1)
    for value in range(1, maximum + 1):
        factorial[value] = factorial[value - 1] * value % MOD
    if maximum > 0:
        inverse_factorial[maximum] = mod_power(factorial[maximum], MOD - 2)
        for value in range(maximum, 0, -1):
            inverse_factorial[value - 1] = inverse_factorial[value] * value % MOD
    return [0 if b < 0 or b > a else factorial[a] * inverse_factorial[b] % MOD * inverse_factorial[a - b] % MOD for a, b in queries]


def main() -> None:
    data = list(map(int, sys.stdin.buffer.read().split()))
    queries = [(data[index], data[index + 1]) for index in range(1, len(data), 2)]
    print('\n'.join(map(str, combination_queries_factorial(queries))))


if __name__ == '__main__':
    main()

复杂度分析

设最大 a 为 N，预处理时间和空间为 O(N)，每个查询 O(1)；最后一次快速幂是 O(log MOD)。

边界与易错点

C(0,0)=1。只有质数模数且阶乘不含该模数因子时，费马逆元才成立；乘法应在每一步取模，不能先做普通整数除法。

模式迁移

大范围、多查询、质数模数是“阶乘加逆元”模板的识别信号；上界更大或模数变化时不能机械套用。回到组合计数。