排列组合

组合数的预计算

组合相关问题中经常用到组合数：

{n \choose k} = \frac{n!}{k!(n-k)!}

因为计算量较大，所以经常需要预计算。当 $n$ 较小的时候（ $n \leq 40$ ），最简单的办法是用Pascal's Triangle来求（简单的DP）：

long long C[MAXN+1][MAXN+1];
int binomial() {
    for (int i = 0; i <= n; i++)
        C[i][0] = C[i][i] = 1;
    for (int i = 0; i <= n; i++) 
        for (int j = 1; j < i; j++)
            if (i != j)
                dp[i][j] = dp[i - 1][j - 1] + dp[i - 1][j];
}

${40 \choose 20} = 137,846,528,820$ 。

当 $n$ 超过这个范围会产生溢出，这时可以用取模方法来计算，或者也往往换成直接用上面的公式计算，因为复杂度更优，使用快速幂之后，复杂度是 $\mathcal{O}(n \log n)$ ：

int fact[500005], invfact[500005];  // factorial and inverse factorial MOD M
const int M = 1e9 + 7;
 
int modpow(int x, int p) {
    if (p == 0) return 1;
    if (p == 1) return x;
    int y = modpow(x, p/2);
    y = (ll)y * y % M;
    return p % 2 ? (ll)y * x % M : y;
}
 
void prepare() {		// 预计算
    fact[0] = fact[1] = 1;
    invfact[0] = invfact[1] = 1;
    for (int i = 2; i <= 500000; i++) {
        fact[i] = ((ll)fact[i-1] * i) % M;
        invfact[i] = modpow(fact[i], M-2);
    }
}
 
int C(int a, int b) {	// 返回组合数
    return (ll)fact[a] * invfact[a-b] % M * invfact[b] % M;
}