笔记汇总

本节将讲解不同情况下 快速预处理排列与组合数 的方法

$P_n^m = \frac{n!}{(n-m)!}$

$C_n^m = \frac{n!}{m!(n-m)!}$

计算的时间复杂度主要与 $m$ 有关。

除数与模数互质 $O(nlogn)$

从 上面的公式 可见，排列与组合数的 预处理 涉及到了 除法取模，所以需要 求逆元

因为用 扩展欧几里得求逆元 的条件是 除数与模数互质。

预处理出符合要求的 $n!$ 和 $n!$ 的逆元即可。

【习题 1】 (代码)

注意点

当 除数 是 模数 的倍数时，不存在逆元。

被除数与模数不互质 $O(n^2)$

组合数有公式 $C_n^m = C_{n-1}^{m-1} + C_{n-1}^m$，且并未涉及除法，

所以我们可以考虑先预处理出 $C_n^m$，然后查表计算。

又因为 $P_n^m = C_n^m * m!$，

所以我们在预处理完 组合数 后也可以顺带计算 排列数

【习题 1】 (代码)

$Lucas$ 定理（模数为质数时）$O(plog_pn)$

$Lucas$ 定理是用来求 $C_n^m \% p$，$p$ 为素数的值。

其结论为 $C_a^b ≡ C_{\frac{a}{p}}^{\frac{b}{p}} * C_{a \% p}^{b \% p}(mod (p))$

由组合数的性质可知 基础 $(basic)$ 是显然的，由于证明需要用到 生成函数，故暂略，下面是性质。

若先将 $a,b$ 用 $p$ 进制表示，则每一次取 $a \% p$ 和 $b \% p$ 时，都相当于取 $a,b$ 这两串 $p$ 进制数的最后一位。

而 $\frac{a}{p}$ 和 $\frac{b}{p}$ 则相当于将 $a,b$ 这两串 $p$ 进制数右移一位。

进而可以 递归 拆解成 $a, b$ 每一位的组合数相乘。

因为这个定理和 模数 $p$ 有关，我们需要分析一下它们之间的 公因数。

对于一个数，只要它的因子里有 质因数 $p$, 它就会被整除。

而右边的哪个式子有一个特点，只要它的两个乘数中有一个有 质因子 $p$，就会被整除。

只有 $b$ 不是 $p$ 的倍数时，才会出现 $C_{a \% p}^{b \% p} > 0$

则 $C_{a \% p}^{b \% p}$ 不能整除 $p$，因为它的因子里不可能有 $p(p 为质数)$。

也就是说如果 $a, b$ 表示的 $p$ 进制数中 $b$ 有为 $0$ 位才 可以整除 $p$

当然如果后面 $b$ 已经没有了，也可以整除 $p$