Lucas 定理

Lucas 定理ψ(｀∇´)ψ

内容ψ(｀∇´)ψ

对于任意质数 $p$ ，存在如下定理：

(\binom{n}{m}) \equiv (\binom{⌊ \frac{n}{p} ⌋}{⌊ \frac{m}{p} ⌋}) \cdot (\binom{n mod p}{m mod p}) (\mod p)

证明ψ(｀∇´)ψ

整个过程极度蜜蜂，不知道咋想出来的。

首先考虑证明一个引理：

I. 对于一个关于 $x$ 的 $p$ 次二项式 $f^{p} (x) = (a x^{n} + b x^{m})^{p}$ ，有： $f^{p} (x) \equiv f (x^{p}) (\mod p)$ 即是 $(a x^{n} + b x^{m})^{p} \equiv (a^{p} x^{p n} + b^{p} x^{p m}) (\mod p)$ 。

我们考虑先证明弱化版本，然后再推广：

II. 对于二项式 $(a + b)^{p}$ ，它在模 $p$ 意义下和 $a^{p} + b^{p}$ 同余。

考虑二项式系数 $(\binom{p}{i})$ 的取值，拆开考虑： $\frac{p!}{i! (p - i)!}$ ，注意到分子只有一个 $p$ ，所以在模 $p$ 意义下，只有当 $i = 0$ 或者 $i = p$ 的时候， $(\binom{p}{i}) = 1$ ，否则等于 $0$ 。

所以代入二项式定理： $(a + b)^{p} \equiv \sum_{i = 0}^{p} (\binom{p}{i}) a^{p - i} b^{i} \equiv \sum_{i = 0}^{p} [i = 0 \lor i = p] a^{p - i} b^{i} \equiv a^{p} + b^{p} (\mod p)$ 。

这里没有使用任何其他有限制的定理，所以这个东西可以比较自然的推广到多项式形式。

然后我们回到原问题，求 $(\binom{n}{m}) mod p$ 本质上是求 $[x^{m}] (1 + x)^{n} \mod p$ ，此时有一个比较蜜蜂的想法，我们考虑把余数分离一下：

\begin{aligned} (1 + x)^{n} & \equiv (1 + x)^{p ⌊ \frac{n}{p} ⌋} (1 + x)^{n mod p} (\mod p) \\ \equiv (1^{p} + x^{p})^{⌊ \frac{n}{p} ⌋} (1 + x)^{n mod p} (\mod p) (use theorem I.) \\ \equiv (1 + x)^{⌊ \frac{n}{p} ⌋} (1 + x)^{n mod p} (\mod p) (use theorem II.) \end{aligned}

然后我们对两边分别看一下贡献： $[x^{m}] (1 + x)^{⌊ \frac{n}{p} ⌋} = (\binom{\frac{n}{p}}{\frac{m}{p}}), [x^{m}] (1 + x)^{n mod p} = (\binom{n mod p}{m mod p})$ 。

由此，可以得到 Lucas 定理的表达式，Q.E.D.

实现ψ(｀∇´)ψ

因为 $n / p$ 的数量级期望显然大于 $n mod p$ ，所以我们预处理模 $p$ 意义下的组合数，前者直接调用，后者递归 $\log p$ 次即可，所以一般来说 Lucas 要求 $p < 10^{5}$ 。

i64 lucas(i64 n, i64 m, i64 p) {
    if(m == 0) return 1ll;
    return (C(n % p, m % p, p) * lucas(n / p, m / p, p)) % p;
}

exLucasψ(｀∇´)ψ

可以对于任意正整数 $p$ 使用的 Lucas。

考虑类似 exCRT 的经典套路，我们分解质因数，用 CRT 构造一个方程然后合并，这样每个方程里面都是一个 Lucas。

也就是，令 $p = \prod_{i = 1}^{r} a_{r}^{c_{r}}$ 。

然后因为任意 $a_{i}^{c_{i}}, a_{j}^{c_{j}}$ 互质，所以我们把他们当作模数。

由 CRT，令 $(\binom{n}{m})$ 为未知数，有：

{\begin{cases} c_{1} & \equiv (\binom{n}{m}) (\mod a_{1}^{c_{1}}) \\ c_{2} & \equiv (\binom{n}{m}) (\mod a_{2}^{c_{2}}) \\ \dots \\ c_{r} & \equiv (\binom{n}{m}) (\mod a_{r}^{c_{r}}) \end{cases}

可以由此解出未知数在模 $p$ 意义下的唯一解 $(\binom{n}{m}) mod p$

最后更新: May 9, 2023