Lucas 定理

Lucas 定理

内容

对于任意质数 \(p\)，存在如下定理：

\[ \dbinom{n}{m} \equiv \dbinom{\lfloor\frac{n}{p}\rfloor}{\lfloor\frac{m}{p}\rfloor} \cdot \dbinom{n \bmod p}{m \bmod p} \pmod p \]

证明

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

首先考虑证明一个引理：

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

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

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

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

所以代入二项式定理：\((a + b)^p \equiv \sum\limits_{i = 0}^p \dbinom{p}{i} a^{p - i}b^i \equiv \sum\limits_{i = 0}^p [i = 0\ \lor\ i = p] a^{p - i}b^i \equiv a^p + b^p \pmod p\)。

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

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

\[ \begin{aligned} (1 + x)^n &\equiv (1 + x)^{p \lfloor\frac{n}{p}\rfloor} (1 + x)^{n \bmod p} \pmod p\\ &\equiv (1^p + x^p)^{\lfloor\frac{n}{p}\rfloor}(1 + x)^{n \bmod p}\pmod p\ (\text{use theorem I.})\\ &\equiv (1 + x)^{\lfloor\frac{n}{p}\rfloor}(1 + x) ^{n \bmod p} \pmod p\ (\text{use theorem II.}) \end{aligned} \]

然后我们对两边分别看一下贡献：\([x^m](1+x)^{\lfloor\frac{n}{p}\rfloor} = \dbinom{\frac{n}{p}}{\frac{m}{p}},[x^m](1 + x)^{n \bmod p} = \dbinom{n\bmod p}{m\bmod p}\)。

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

实现

因为 \(n / p\) 的数量级期望显然大于 \(n \bmod 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\limits_{i = 1}^ra_{r}^{c_r}\)。

然后因为任意 \(a_{i}^{c_i}, a_{j}^{c_j}\) 互质，所以我们把他们当作模数。

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

\[ \begin{cases} c_1 &\equiv \dbinom{n}{m} \pmod {a_{1}^{c_1}} \\ c_2 &\equiv \dbinom{n}{m} \pmod {a_{2}^{c_2}} \\ &\cdots\\ c_r &\equiv \dbinom{n}{m} \pmod {a_{r}^{c_r}} \end{cases} \]

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

---

最后更新: May 9, 2023