基于快速幂求逆元, \(O(1)\) 查询， \(O(n)\) 预处理.

使用前先调用 q_inv(max_of_n).

#include <vector>
long long qpow(long long a, long long k) {
    using LL = long long;
    LL ans = 1;
    while (k) {
        if (k & 1)
            ans = ans * a % Mod;
        a = a * a % Mod;
        k >>= 1;
    }
    return ans;
}

std::vector<int> inv, in;
void q_inv(int n) {
    using LL = long long;
    inv.resize(n + 10), in.resize(n + 10);
    in[0] = in[1] = inv[0] = 1;
    for (LL i = 2; i <= n; i++) {
        in[i] = in[i - 1] * i % Mod;
    }
    inv[n] = qpow(in[n], Mod - 2);
    for (LL i = n; i > 1; i--) {
        inv[i - 1] = inv[i] * i % Mod;
    }
}

/// @brief 组合数C_a^b mod Mod
/// @param a 下标
/// @param b 上标
/// @return rt
inline long long C_q(int a, int b) {
    return 1LL * in[a] * inv[a - b] % Mod * inv[b] % Mod;
}