非取模的组合数

基于公式$\binom{n}{m}=\frac{n!}{m!(n-m)!}$

时间复杂度$O(m)$，当计算$\binom{30}{15}=155117520$ 时，正溢出了long long型，所以答案计算不正确

using ll = long long;
ll comb(ll n, ll m) {
    ll a = 1, b = 1;
    for (ll i=n,j=1; i>n-m; i--,j++) {
        a *= i;
        b *= j;
    }
    return a/b;
}

基于公式$\binom{n}{m}=\frac{n-m+1}{m}\binom{n}{m-1}$

时间复杂度$O(m)$，能够计算更大的组合数

// comb(n, m) = (n-m+1)/m * comb(n, m-1)
// comb(n, m-1)是整数，(n-m+1)*comb(n, m-1)是整数，(n-m+1)*comb(n, m-1)/m是整数
// comb(n, m-1) = (n-m+2)/(m-1) * comb(n, m-2)

ll comb(ll n, ll m) { // m <= n;
    if (m == 0) return 1;
    return comb(n, m-1)*(n-m+1)/m;
}
ll comb(ll n, ll m) {
    ll rt = 1;
    for (ll i=n,j=1; i>n-m; i--,j++) {
        rt = rt*i/j;
    }
    return rt;
}

取模的组合数

线性预处理逆元求组合数

时间复杂度$O(n)$

using ll = long long;
const ll MOD = 1e9+7;
// O(n)
ll C(ll n, ll m) { //n个里选m个
    ll inv[n+1];
    inv[1] = 1;
    for (int i=2; i<=n; i++) {
            inv[i] = (MOD-MOD/i)*inv[MOD%i]%MOD;
    }
    ll rt = 1;
    for (int i=m; i>0; i--) {
        rt = rt*(n-i+1)%MOD*inv[i]%MOD;
    }
    return rt;
}

阶乘逆元求组合数

$n! \equiv (n+1)!^{-1}*(n+1) \pmod p$

预处理$O(n)$打表

using ll = long long;
const ll MOD = 1e9+7;
#define N 100005
ll fac[N], inv_fac[N];
ll fpow(ll x, ll p, ll m) {
	ll rt = 1;
	while (p) {
		if (p&1) rt *= x, rt %= m;
		x *= x; x %= m;
		p >>= 1;
	}
	return rt;
}
void pre() {
    fac[0] = 1;
    for (int i=1; i<N; i++) {
        fac[i] = fac[i-1]*i%MOD;
    }
    inv_fac[N-1] = fpow(fac[N-1], MOD-2, MOD);
    for (int i=N-2; i>=0; i--) {
        inv_fac[i] = inv_fac[i+1]*(i+1)%MOD;
    }
}
// O(1)
int comb(int n, int m) {
		return fac[n]*inv_fac[m]%MOD*inv_fac[n-m]%MOD;
}

大组合数

求大组合数$\binom{n}{m}$，若m较小，n巨大，则可以$O(n)$求出。

using ll = long long;

ll fpow(ll x, ll p, ll MOD) {
    ll rt = 1;
    while (p) {
        if (p&1) rt *= x, rt %= MOD;
        x *= x;
        x %= MOD;
        p >>= 1;
    }
    return rt;
}

// n!/(m!(n-m)!)
ll comb(ll n, ll m, ll MOD) {
    ll u = 1, d = 1;
    for (ll i = n; i>n-m; i--) {
        u = u*i%MOD;
        d = d*(i-n+m)%MOD;
    }
    return u*fpow(d, MOD-2, MOD)%MOD;
}

模较小质数p=O(1e5)，用卢卡斯定理