求模数非质数的组合数c++

可以使用 Lucas 定理求解组合数，其中需要使用到模数的逆元。以下是一个求解组合数模数为非质数的实现示例：

#include <iostream>
#include <vector>

using namespace std;

const int mod = 998244353;

// 求 a 的 b 次幂对 p 取模的结果
int pow_mod(int a, int b, int p) {
    int res = 1 % p;
    while (b) {
        if (b & 1) res = (long long) res * a % p;
        a = (long long) a * a % p;
        b >>= 1;
    }
    return res;
}

// 求模数的逆元
int inv(int a, int p) {
    return pow_mod(a, p - 2, p);
}

// 预处理阶乘和阶乘的逆元
void init(vector<int>& fac, vector<int>& inv_fac, int n) {
    fac[0] = inv_fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = (long long) fac[i - 1] * i % mod;
        inv_fac[i] = inv(fac[i], mod);
    }
}

// 计算组合数
int C(int n, int m, vector<int>& fac, vector<int>& inv_fac) {
    if (m > n) return 0;
    return (long long) fac[n] * inv_fac[m] % mod * inv_fac[n - m] % mod;
}

// 计算 Lucas 数
int Lucas(int n, int m, vector<int>& fac, vector<int>& inv_fac) {
    if (m == 0) return 1;
    return (long long) C(n % mod, m % mod, fac, inv_fac) * Lucas(n / mod, m / mod, fac, inv_fac) % mod;
}

int main() {
    int n, m;
    cin >> n >> m;

    vector<int> fac(n + 1), inv_fac(n + 1);
    init(fac, inv_fac, n);

    cout << Lucas(n, m, fac, inv_fac) << endl;

    return 0;
}

需要注意的是，这里使用了 998244353 作为模数，如果需要使用其他模数，需要修改 `mod` 的值。