组合数学

组合数

组合数 $\binom{a}{b}$ 或 $C_a^b$，表示从 $a$ 个不同的物品中选出 $b$ 个物品，不考虑 $b$ 个物品之间的相对顺序，总的方案数。

\[ \begin{align*} \binom{a}{b}=&\ \frac{\prod_{i\in [a-b+1,a]}{i}}{\prod_{i\in [1,b]}{i}}\\ =&\ \frac{a!}{(a-b)!b!} \end{align*} \]

当 $p$ 为质数： $$ \binom{a}{b}\bmod p=\binom{a\bmod p}{b\bmod p}\times \binom{\frac{a}{p}}{\frac{b}{p}} \bmod p $$

此定理可用以在预处理后以 $O\big(\log_p{\min(a,b)}\big)$ 的时间复杂度求出 $\binom{a}{b}$。