本页面大量引用 OI Wiki

组合数 $C_n^m$ 常用符号 $\dbinom{n}{m}$ 来表示，读作"$n$ 选 $m$"。

组合数经典性质

选出 $m$ 相当于选出 $n-m$ 个排除：

$\dbinom{n}{m}=\dbinom{n}{n-m}$

组合数的递推式（杨辉三角）：

$\dbinom{n}{m}=\dbinom{n-1}{m}+\dbinom{n-1}{m-1}$

基础性质（杨辉三角的一行）：

$\dbinom{n}{0}+\dbinom{n}{1}+\dots+\dbinom{n}{n}=\sum_{i=0}^n\dbinom{n}{i}=2^n$

范德蒙德恒等式：

$\sum_{i=0}^k\dbinom{n}{i}\dbinom{m}{k-i}=\dbinom{m+n}{k}$

二项式定理

$(a+b)^n=\sum_{i=0}^n\dbinom{n}{i}a^{n-i}b^i$

二项式反演

记 $f_n$ 表示恰好使用 $n$ 个不同元素形成特定结构的方案数，$g_n$ 表示从 $n$ 个不同元素中选出 $i \geq 0$ 个元素形成特定结构的总方案数。

若已知 $f_n$ 求 $g_n$：

$g_n = \sum_{i = 0}^{n} \binom{n}{i} f_i$

若已知 $g_n$ 求 $f_n$（二项式反演）：

$f_n = \sum_{i = 0}^{n} \binom{n}{i} (-1)^{n-i} g_i$

狄利克雷卷积

数论函数 $f(n)$ 和 $g(n)$ 的 Dirichlet 卷积，记作 $f \ast g$，定义为：

$(f \ast g)(n) = \sum_{k\mid n}f(k)g\left(\dfrac{n}{k}\right) = \sum_{k\ell=n}f(k)g(\ell)$

莫比乌斯反演

莫比乌斯函数

莫比乌斯函数 $\mu(n)$ 定义为：

\mu(n)= \begin{cases} 1,&n=1,\\ 0,&n\text{ 是某个质数平方的倍数},\\ (-1)^k,&n \text{ 是 } k \text{ 个不同质数的乘积}. \end{cases}

莫比乌斯反演

设 $f(n),g(n)$ 是两个数论函数：

$f(n) = \sum_{d\mid n}g(d) \iff g(n) = \sum_{d\mid n}\mu\left(\dfrac{n}{d}\right)f(d)$

扩展

$f(n) = \sum_{n\mid d}g(d) \iff g(n) = \sum_{n\mid d}\mu\left(\dfrac{d}{n}\right)f(d)$

组合数计算

递推求组合数

const int MAXN = 2000;
int C[MAXN + 5][MAXN + 5];

void init()
{
    for (int i = 0; i <= MAXN; i++)
    {
        C[i][0] = C[i][i] = 1;
        for (int j = 1; j < i; j++)
            C[i][j] = (C[i - 1][j] + C[i - 1][j - 1]) % MOD;
    }
}

阶乘逆元求组合数

// fact[i] = i! % MOD, invFact[i] = (i!)^-1 % MOD
int C(int n, int m)
{
    if (n < m || m < 0)
        return 0;
    return fact[n] * invFact[m] % MOD * invFact[n - m] % MOD;
}