卢卡斯(Lucas)定理

数学 组合数学 算法

---

主页地址 ：月光森林

---

引入

之前有写过一篇博客是求组合数（取模）的两种方法。那篇文章里介绍的方法其实也还有局限性，Pascal打表由于内存的限制一般只用于求取1000以内的组合数，而使用逆元套公式的方法其实也只适用于求取的组合数 $C(n, m) \% p$ 中，n 和 m均不大于要求的模数 p 。这样就导致了一个很尴尬的问题——如果要求取的组合数超过了模数p，这个时候有要怎么办呢。本人之前由于水平限制并没有了解到这个问题，前几天打玲珑杯#round 4的时候被这个问题困扰了，经队友提醒才知道有Lucas定理这种东西。这里就另写一篇文章，其实是作为之前的“组合数取模的两种方法”的一个拓展篇。将这个问题一次性终结到底。

定义、证明与方法

卢卡斯(Lucas)定理
设 $P$ 为素数，$a, b \in N^*$ ,并且

$$a = a_kp^k + a_{k - 1}p^{k-1} + \dots + a_1p+ a_0 \\ b = b_kp^k + b_{k-1}p^{k-1} + \cdots + b_1p + b_0$$
这里 $0 \leq a_i, b_i \leq p - 1$ 都是整数，$i = 0,1,2, \cdots, k$. 则有
$$C_a^b \equiv C_{a_k}^{b_k} * C_{a_{k-1}}^{b_{k-1}} * \cdots * C_{a_0}^{b_0} (mod \ P)$$

这里还要声明一点，本篇博客的参考书籍为冯志刚版《初等数论》第37页，下面给出原书的证明：

这个定理的意义就在于把 $a$ 或者 $b$ 或者两者均大于 $p$ 的组合数 $C_a^b$ 转换为求解小于 $p$ 的整数 $a_k$ 和 $b_k$ 的组合数 $C_{a_k}^{b_k}$ 的乘积。

而对于 $a_0, a_1, \cdots, a_k$ 可以通过秦九韶算法:

$$a = (((\cdots (0 * p + a_k) \cdots)* p + a_2) * p + a_1) * p + a_0$$
逆向得到，即
$$a_0 = (a / p^0) \% p \\ a_1 = (a / p^1) \% p \\ a_2 = (a / p^2) \% p \\ \vdots \\ a_k = (a / p^k) \% p$$
显然，秦九韶的逆向算法页同样适用于求解 $b$.

使用解析

实际求解 $C_a^b$ 时，只要 $a_i$ 和 $b_i$ 当中有一个仍然大于 $p$，就要继续使用逆向的秦九韶算法。但实际编写代码的过程，只需要递归即可：

LL Lucas(LL a, LL b)
{
    if(a < mod && b < mod)
        return C(a, b);
    return
        C(a % mod, b % mod) * Lucas(a / mod, b / mod);
}

其中C(a, b)的函数在之前的文章求组合数（取模）的两种方法叙述过了，这里就不继续赘述了。

现在，通过pascal打表的方法在 $O(1)$ 的时间里求得小范围的组合数，用逆元的方法可以求取模数范围内的组合数，在加上Lucas定理，就可以求取任意范围内的组合数了。

在实际运用的过程中，可以根据实际判断哪种方法最适合，$a, b$ 的是一个主导因素，同事，算法的简单性也是一个主导因素。毕竟，越简单的东西越不容易出错。杀鸡用牛刀不是不可以，但是你想过鸡的感受么。。。

以上です～