c++组合数（逆元）代码

const int MAXN = 1e6 + 5;
const int MOD = 998244353;

int fac[MAXN], inv[MAXN];

int qpow(int a, int b) {
    int res = 1;
    while (b) {
        if (b & 1) res = 1ll * res * a % MOD;
        a = 1ll * a * a % MOD;
        b >>= 1;
    }
    return res;
}

void init() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++) fac[i] = 1ll * fac[i - 1] * i % MOD;
    inv[MAXN - 1] = qpow(fac[MAXN - 1], MOD - 2);
    for (int i = MAXN - 2; i >= 0; i--) inv[i] = 1ll * inv[i + 1] * (i + 1) % MOD;
}

int C(int n, int m) {
    return n < m ? 0 : 1ll * fac[n] * inv[m] % MOD * inv[n - m] % MOD;
}

相关问题

扩展欧几里得算法求逆元c++c++

欧几里得算法可以用来求解两个数的最大公约数，而扩展欧几里得算法则可以在求解最大公约数的同时，找到使得两个数的线性组合等于最大公约数的系数。下面是用C++实现的扩展欧几里得算法来求逆元的示例代码：

#include <iostream>

using namespace std;

int extendedEuclidean(int a, int b, int& x, int& y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    
    int x1, y1;
    int gcd = extendedEuclidean(b, a % b, x1, y1);
    
    x = y1;
    y = x1 - (a / b) * y1;
    
    return gcd;
}

int inverseModulo(int a, int m) {
    int x, y;
    int gcd = extendedEuclidean(a, m, x, y);
    
    if (gcd != 1) {
        throw "Inverse does not exist.";
    }
    
    return (x % m + m) % m;
}

int main() {
    int a, m;
    cout << "Enter the number and modulo: ";
    cin >> a >> m;
    
    try {
        int inv = inverseModulo(a, m);
        cout << "The inverse of " << a << " modulo " << m << " is: " << inv << endl;
    } catch(const char* msg) {
        cerr << msg << endl;
    }
    
    return 0;
}

这段代码通过扩展欧几里得算法求解了给定数的逆元，并进行了异常处理，以确保逆元存在。用户可以输入一个数和一个模数，程序将输出给定数的逆元。

求模数非质数的组合数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` 的值。