信息学竞赛模板（十六）— 组合计数

普通形式

对每个要乘或除的数进行分解质因数，最后求质因数的快速幂累乘结果

typedef long long LL;
int a[70];

//快速幂
LL qpow(LL a, int n) {
    LL s = 1;
    while (n) {
        if (n & 1) s *= a;
        a *= a;
        n >>= 1;
    }
    return s;
}

//分解质因数
void divd(int x, int v) {
    for (int i = 2; i <= x; i++) {
        if (x % i == 0) {
            while (x % i == 0) {
                a[i] += v;
                x /= i;
            }
        }
    }
    if (x > 1) a[x] += v;
}

//求组合数 C(n,m)
LL C(int n, int m) {
    if (n < m) return 0;
    if (m == 1) return n;
    if (m == n) return 1;
    memset(a, 0, sizeof a);
    LL ans = 1;
    for (int i = n - m + 1; i <= n; i++) divd(i, 1);
    for (int i = 2; i <= m; i++) divd(i, -1);
    for (int i = 2; i <= 65; i++) {
        if (a[i]) ans *= qpow(i, a[i]);
    }
    return ans;
}

求余形式

版本一 — 杨辉三角、dp

利用杨辉三角的性质，简洁快速写出 $n \le 2\times10^4$ 的递推形式，极限耗时 600 ms

const int MOD = 1e9 + 7, N = 100005;
int n, f[N];

int C(int n, int m) {
    if (n < m) return 0;
    if (m == 0 || m == n) return 1;

    for (int i = 1; i <= n; i++) {
        f[0] = f[i] = 1;
        for (int j = i - 1; j; j--) {
            f[j] = (f[j] + f[j - 1]) % MOD;
        }
    }
    return f[m];
}

版本二 — 乘法逆元

对除法使用乘法逆元进行替换，逆元用快速幂求得，并先进行预处理，降低时间复杂度，适用于 $n \le 4\times10^6$，极限耗时 740 ms

const int N = 1e5 + 5, MOD = 998244353;
int invp[N], p[N];

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

//预处理阶乘和逆元阶乘
void pre(int n) {
    p[0] = 1;
    invp[0] = 1;
    for (int i = 1; i <= n; i++) {
        p[i] = p[i - 1] * 1ll * i % MOD;
        invp[i] = invp[i - 1] * 1ll * qpow(i, MOD - 2) % MOD;
    }
}

int C(int n, int m) {
    if (n < m) return 0;
    if (n == m || m == 0) return 1;

    int ans = 1;
    ans = ans * 1ll * p[n] % MOD;
    ans = ans * 1ll * invp[m] % MOD;
    ans = ans * 1ll * invp[n - m] % MOD;
    return ans;
}