高效计算组合数的阶乘逆元线性推导与实现

核心逻辑与数学原理

在 NOIP 级别的组合计数问题中，经常需要在大数取模（模数 $M$ 通常为 $998244353$ 或 $10^9+7$ 等大质数）的约束下计算组合数：

$$C_n^m = \frac{n!}{m!(n-m)!}$$

由于涉及除法运算，在模意义下无法直接进行分子分母的逐步取模。必须将除法转化为乘法，即乘以分母的乘法逆元：

$$C_n^m \equiv n! \cdot [m!]^{-1} \cdot [(n-m)!]^{-1} \pmod M$$

只要能够高效求出阶乘的逆元，就能在 $O(1)$ 的时间内高频响应任意组合数的查询。

如果对每个询问或每个阶乘独立使用快速幂（费马小定理）求解逆元，单次复杂度为 $O(\log M)$。在 $N \le 10^7$ 且多组询问的极限场景下，这会导致总时间复杂度退化而引发 TLE。因此，必须引入阶乘逆元线性逆推技术。

算法推导与状态设计

为了在 $O(N)$ 时间内离线处理出 $1 \sim N$ 所有阶乘的逆元，我们需要利用逆元的反向递推关系。

设 $fact[i] = i! \bmod M$ 为阶乘数组， $invFact[i] = [i!]^{-1} \bmod M$ 为阶乘逆元数组。

根据阶乘的定义：

$$fact[i] = fact[i-1] \cdot i$$

我们在等式两边同时取逆元：

$$[fact[i]]^{-1} \equiv [fact[i-1] \cdot i]^{-1} \pmod M$$

$$invFact[i] \equiv invFact[i-1] \cdot i^{-1} \pmod M$$

为了实现线性不依赖单点逆元，我们将等式两边同时乘以 $i$：

$$invFact[i] \cdot i \equiv invFact[i-1] \cdot i^{-1} \cdot i \pmod M$$

$$invFact[i-1] \equiv invFact[i] \cdot i \pmod M$$

算法执行状态设计

正向预处理：从 $1$ 到 $N$ 递推计算出标准的阶乘数组 $fact[i]$。
单点突破：仅对最大边界 $N$ 的阶乘 $fact[N]$ 调用一次快速幂（费马小定理），算出 $invFact[N] = (fact[N])^{M-2} \bmod M$。
逆向拓扑线性递推：利用刚才推导出的状态转移方程，从 $N$ 开始向 $1$ 反向循环：

$$invFact[i-1] = invFact[i] \cdot i \bmod M$$

在反向扫描的过程中，顺便可以顺手带出单个元素的逆元（若题目有刚需）：$i^{-1} = invFact[i] \cdot fact[i-1] \bmod M$。

C++ 标准源码

#include <iostream>
#include <vector>

const int MOD = 998244353; // 生产环境常见高频质数模数
const int MAXN = 5000000;  // 模拟 NOIP 极限数据范围

long long fact[MAXN + 5];
long long invFact[MAXN + 5];

// 费马小定理快速幂
long long quick_power(long long base, long long exp) {
    long long res = 1;
    base %= MOD;
    while (exp > 0) {
        if (exp & 1) res = (res * base) % MOD;
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return res;
}

// 阶乘与阶乘逆元双向线性预处理核心
void init_combinatorics(int n) {
    fact[0] = 1;
    invFact[0] = 1;
    for (int i = 1; i <= n; ++i) {
        fact[i] = (fact[i - 1] * i) % MOD;
    }

    // 核心断点：仅对最后一个元素求一次大快幂
    invFact[n] = quick_power(fact[n], MOD - 2);

    // 反向拉平整体阶乘逆元链条
    for (int i = n; i >= 1; --i) {
        invFact[i - 1] = (invFact[i] * i) % MOD; // 致命注意：此处乘以的是 i，而不是 inv[i]
    }
}

// O(1) 响应组合数查询
long long query_C(int n, int m) {
    if (m < 0 || m > n) return 0; // 边界防御性拦截
    return fact[n] * invFact[m] % MOD * invFact[n - m] % MOD;
}

int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n = MAXN;
    init_combinatorics(n);

    int queries;
    if (std::cin >> queries) {
        while (queries--) {
            int qn, qm;
            std::cin >> qn >> qm;
            std::cout << query_C(qn, qm) << "\n";
        }
    }
    return 0;
}

NOIP 实战避坑指南

反向递推时公式乘数写错 在执行反向递推 invFact[i-1] = invFact[i] * i % MOD 时，部分选手容易在脑海中混淆概念，顺手写成了 invFact[i-1] = invFact[i] * inv[i] % MOD。这会导致逆元数组直接塌陷。一定要记住：阶乘逆元的反向递推乘的是原数 $i$，而非 $i$ 的逆元。
数组边界越界与 $fact[0]$ 漏初始化 在处理诸如 $C_n^0$ 或 $C_n^n$ 的极端情况时，计算公式会转换为求 invFact[0]。如果忘记初始化 fact[0] = 1 和 invFact[0] = 1，或者在反向循环中没有将 $0$ 的状态安全推出，这些特殊组合数将会乘上未初始化的内存垃圾值 $0$，引发致命的逻辑溃败。

经典 NOIP/洛谷真题

1. 洛谷 P3197 [HNOI2008] 越狱

题意描述：有 $M$ 种宗教，$N$ 个囚犯排成一排。每个囚犯选择一种宗教。如果相邻囚犯的宗教相同，就会发生越狱。求有多少种可能发生越狱的施暴方案。结果对 $100003$ 取模。
问题本质：正难则反，组合数学的总集减去不合法集。
核心解题思路：总方案数为 $M^N$。不发生越狱的方案数（即相邻人宗教均不同）为 $M \cdot (M-1)^{N-1}$。则发生越狱的方案数为 $M^N - M \cdot (M-1)^{N-1}$。直接使用快速幂求解。注意减法取模时要加上模数防止负数出现：(ans % MOD + MOD) % MOD。

2. 洛谷 P2822 组合数问题（NOIP 2016 提高组）

题意描述：给定 $n, m$ 和固定常数 $k$，要求出对于所有的 $0 \le i \le n, 0 \le j \le \min(i, m)$，有多少对 $(i, j)$ 满足 $C_i^j$ 是 $k$ 的倍数。多组询问，$n, m \le 2000$。
问题本质：杨辉三角动态规划地推与二维前缀和。
核心解题思路：注意本题的模数 $k$ 不是固定的大质数，甚至非常小，因此绝对不能使用上面的逆元算法。由于 $n, m \le 2000$ 规模较小，直接采用杨辉三角递推公式 $C_i^j = (C_{i-1}^{j-1} + C_{i-1}^j) \bmod k$。若运算后结果为 $0$，说明其能被 $k$ 整除。接着使用二维前缀和构建统计矩阵，即可在 $O(N^2)$ 预处理后，以 $O(1)$ 的速度回答每一组询问。