求组合数的几种方法

1.预处理出1~n的阶乘与1~n的阶乘的逆元

// 预处理阶乘和阶乘逆元的数组
vector<int> fac, invfac;
int power(int a, int b) {
    int res = 1;
    while (b) {
        if (b % 2) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return res;
}

void init(int n) {
    fac.resize(n + 1);
    invfac.resize(n + 1);

    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = 1LL * fac[i - 1] * i % mod;
    }
    invfac[n] = power(fac[n], mod - 2);  // 使用费马小定理求逆元
    for (int i = n - 1; i >= 0; i--) {
        invfac[i] = 1LL * invfac[i + 1] * (i + 1) % mod;
    }
}

// 计算组合数 C(n, m)
int binom(int n, int m) {
    if (n < m || m < 0) return 0;
    return 1LL * fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}

2.递推法 (C(n,m) = C(n - 1, m - 1) + C(n - 1, m) )

int getC() {
    for(int i = 0; i <= N; i++) {

        for(int j = 0; j <= i; j++) {
            if(j == 0) C[i][j] = 1;
            else (C[i][j] = C[i - 1][j - 1] + C[i - 1][j]) % mod;
        }
    }
}

3.卢卡斯定理 (适合求模数较小且模数为质数时使用)

C(n, m) = C(n/p, m / p) * C(n % p, m % p) (mod p)

vector<int> fac, invfac;
int power(int a, int b) {
    int res = 1;
    while (b) {
        if (b % 2) res = 1LL * res * a % mod;
        a = 1LL * a * a % mod;
        b >>= 1;
    }
    return res;
}

void init(int n) {
    fac.resize(n + 1);
    invfac.resize(n + 1);

    fac[0] = 1;
    for (int i = 1; i <= n; i++) {
        fac[i] = 1LL * fac[i - 1] * i % mod;
    }
    invfac[n] = power(fac[n], mod - 2);  // 使用费马小定理求逆元
    for (int i = n - 1; i >= 0; i--) {
        invfac[i] = 1LL * invfac[i + 1] * (i + 1) % mod;
    }
}


int C(int n, int m) {
    if (n < m || m < 0) return 0;
    return 1LL * fac[n] * invfac[m] % mod * invfac[n - m] % mod;
}

int lucas(long long a, long long b)
{
    if (a < mod && b < mod) return C(a, b);
    return (long long)C(a % mod, b % mod) * lucas(a / mod, b / mod) % mod;
}

原文地址：https://blog.csdn.net/bawangtianzun/article/details/142876077

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！