卢卡斯定理学习笔记

引入

Lucas 定理用于求解大组合数取模的问题，其中模数必须为素数。正常的组合数运算可以通过递推公式求解，但当问题规模很大，而模数是一个不大的质数的时候，就不能简单地通过递推求解来得到答案，需要用到 Lucas 定理。

定义

Lucas 定理内容如下：对于质数 $p$ ，有

(\binom{n}{m}) mod p = (\binom{⌊ n / p ⌋}{⌊ m / p ⌋}) \cdot (\binom{n mod p}{m mod p}) mod p

观察上述表达式，可知 $n mod p$ 和 $m mod p$ 一定是小于 $p$ 的数，可以直接求解， $(\binom{⌊ n / p ⌋}{⌊ m / p ⌋})$ 可以继续用 Lucas 定理求解。这也就要求 $p$ 的范围不能够太大，一般在 $10^{5}$ 左右。边界条件：当 $m = 0$ 的时候，返回 $1$ 。

时间复杂度为 $O (f (p) + g (n) \log n)$ ，其中 $f (n)$ 为预处理组合数的复杂度， $g (n)$ 为单次求组合数的复杂度。

证明

考虑 $(\binom{p}{n}) mod p$ 的取值，注意到 $(\binom{p}{n}) = \frac{p!}{n! (p - n)!}$ ，分子的质因子分解中 $p$ 的次数恰好为 $1$ ，因此只有当 $n = 0$ 或 $n = p$ 的时候 $n! (p - n)!$ 的质因子分解中含有 $p$ ，因此 $(\binom{p}{n}) mod p = [n = 0 \lor n = p]$ 。进而我们可以得出

\begin{aligned} (a + b)^{p} & = \sum_{n = 0}^{p} (\binom{p}{n}) a^{n} b^{p - n} \\ \equiv \sum_{n = 0}^{p} [n = 0 \lor n = p] a^{n} b^{p - n} \\ \equiv a^{p} + b^{p} (\mod p) \end{aligned}

注意过程中没有用到费马小定理，因此这一推导不仅适用于整数，亦适用于多项式。因此我们可以考虑二项式 $f^{p} (x) = (a x^{n} + b x^{m})^{p} mod p$ 的结果

\begin{aligned} (a x^{n} + b x^{m})^{p} & \equiv a^{p} x^{p n} + b^{p} x^{p m} \\ \equiv a x^{p n} + b x^{p m} \\ \equiv f (x^{p}) \end{aligned}

考虑二项式 $(1 + x)^{n} mod p$ ，那么 $(\binom{n}{m})$ 就是求其在 $x^{m}$ 次项的取值。使用上述引理，我们可以得到

\begin{aligned} (1 + x)^{n} & \equiv (1 + x)^{p ⌊ n / p ⌋} (1 + x)^{n mod p} \\ \equiv (1 + x^{p})^{⌊ n / p ⌋} (1 + x)^{n mod p} \end{aligned}

注意前者只有在 $p$ 的倍数位置才有取值，而后者最高次项为 $n mod p \leq p - 1$ ，因此这两部分的卷积在任何一个位置只有最多一种方式贡献取值，即在前者部分取 $p$ 的倍数次项，后者部分取剩余项，即 $(\binom{n}{m}) mod p = (\binom{⌊ n / p ⌋}{⌊ m / p ⌋}) \cdot (\binom{n mod p}{m mod p}) mod p$ 。

exLucas 定理

Lucas 定理中对于模数 $p$ 要求必须为素数，那么对于 $p$ 不是素数的情况，就需要用到 exLucas 定理。

卢卡斯定理 学习笔记 ​

引入 ​

定义 ​

证明 ​

exLucas 定理 ​

卢卡斯定理学习笔记

引入

定义

证明

exLucas 定理