笔记汇总
本节将讲解不同情况下 快速预处理排列与组合数 的方法
$P_n^m = \frac{n!}{(n-m)!}$
$C_n^m = \frac{n!}{m!(n-m)!}$
计算的时间复杂度主要与 $m$ 有关。
除数与模数互质 $O(nlogn)$
从 上面的公式 可见，排列与组合数的 预处理 涉及到了 除法取模，所以需要 求逆元
因为用 扩展欧几里得求逆元 的条件是 除数与模数互质。
预处理出符合要求的 $n!$ 和 $n!$ 的逆元即可。
注意点
当 除数 是 模数 的倍数时，不存在逆元。
被除数与模数不互质 $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!$，
所以我们在预处理完 组合数 后也可以顺带计算 排列数
$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$
