组合数预处理：O(n)时间复杂度下的高效计算

在信息学奥赛 CSP-J 中，组合数的计算是一个常见且重要的考点。特别是在模意义下，如何快速准确地计算组合数 C(n, k) 是许多考生需要掌握的技能。本文将介绍一种基于阶乘与逆元的线性预处理方法，能够在 O(n) 的时间复杂度内完成组合数的预处理，从而在查询时实现 O(1) 的时间复杂度。

一、阶乘与逆元的预处理

在模意义下计算组合数 C(n, k)，我们通常使用以下公式：

C(n, k) = n! / (k! * (n-k)!)

其中，n! 表示 n 的阶乘，即 n × (n-1) × … × 1。为了快速计算组合数，我们可以预先计算出所有阶乘及其逆元。

1. 阶乘的预处理

我们定义一个数组 fact[i] 表示 i 的阶乘在模 p 下的值，即：

fact[i] = i! % p

通过迭代计算，我们可以在 O(n) 的时间内完成阶乘的预处理：

const int MAXN = 1e5 + 5;
const int MOD = 1e9 + 7;
long long fact[MAXN];

void preprocess_factorials(int n, int p) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = fact[i - 1] * i % p;
    }
}

2. 逆元的预处理

逆元的计算可以使用费马小定理或扩展欧几里得算法。这里我们使用费马小定理，该定理在模 p 为质数时成立，表示为：

a^(p-1) ≡ 1 (mod p)

因此，a 的逆元可以表示为：

a^(-1) ≡ a^(p-2) (mod p)

我们可以通过快速幂算法在 O(log p) 的时间内计算出 a 的逆元。为了在 O(n) 的时间内预处理所有逆元，我们可以迭代计算：

long long inv_fact[MAXN];

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = result * base % mod;
        }
        base = base * base % mod;
        exp /= 2;
    }
    return result;
}

void preprocess_inverse_factorials(int n, int p) {
    inv_fact[n] = mod_pow(fact[n], p - 2, p);
    for (int i = n - 1; i >= 0; --i) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % p;
    }
}

二、组合数的快速计算

在完成阶乘和逆元的预处理后，我们可以使用以下公式在 O(1) 的时间内计算组合数 C(n, k)：

C(n, k) = fact[n] * inv_fact[k] % p * inv_fact[n - k] % p

三、预处理代码模板

以下是完整的预处理代码模板：

#include <iostream>
using namespace std;

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

long long mod_pow(long long base, long long exp, long long mod) {
    long long result = 1;
    while (exp > 0) {
        if (exp % 2 == 1) {
            result = result * base % mod;
        }
        base = base * base % mod;
        exp /= 2;
    }
    return result;
}

void preprocess(int n, int p) {
    fact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = fact[i - 1] * i % p;
    }
    inv_fact[n] = mod_pow(fact[n], p - 2, p);
    for (int i = n - 1; i >= 0; --i) {
        inv_fact[i] = inv_fact[i + 1] * (i + 1) % p;
    }
}

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

int main() {
    int n, q, p = MOD;
    cin >> n >> q;
    preprocess(n, p);
    while (q--) {
        int a, b;
        cin >> a >> b;
        cout << combination(a, b, p) << endl;
    }
    return 0;
}

四、总结

通过上述方法，我们可以在 O(n) 的时间复杂度内预处理阶乘和逆元，并在 O(1) 的时间复杂度内查询任意组合数 C(n, k)。这种方法在处理大量查询时具有显著的优势，是 CSP-J 备考中不可或缺的技巧之一。

希望本文能帮助各位考生更好地理解和掌握组合数的预处理方法，为信息学奥赛 CSP-J 取得好成绩打下坚实的基础。

喵呜刷题：让学习像火箭一样快速，快来微信扫码，体验免费刷题服务，开启你的学习加速器！