Lucas定理 - 组合数学中的一个重要基本定理

发表于 更新于 本文字数： 1.7k 阅读时长 ≈ 6 分钟

Lucas定理（Lucas Theorem）是组合数学中一个重要的基本定理。它允许我们利用计算机快速求出模p意义下（其中p为质数）的组合数的值。

​ 在使用计算机求解组合数时，常使用下列式子（可由Lucas定理推得）：

\(C_n^m \equiv C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor} * C_{n \mod p}^{m \mod p}\mod p\)​

​ 下文中记 \(C_n^m\) 为C(m,n)，且规定当n < m时，C(m,n) = 0。

​ 不妨暂时称上述公式为Lucas同余式。此公式允许我们递归地求出C(m,n)在模p意义下的值。

​ 由于其证明涉及大量数学知识，在此略过（感兴趣的同学可以自己搜索Lucas定理的证明过程，一般会利用到二项式定理进行构造性证明，并且证明过程中包含一些重要推论）。

​ 可能我们看到这里时，会问一个问题：为什么要大费周章使用Lucas定理求解呢？

​ 大部分时候，我们会采用费马小定理求模p意义下的逆元：整数x的逆元为\(x^{p-2}\)。求解时可利用快速幂进行优化，单次求解的复杂度为O(\(log_2p\))，时间效率上相当优秀（也可以采用递推的方法求解某个连续自然数段floor~ceil的逆元，其复杂度为O(ceil - floor)即O(n)，达到线性程度。由于篇幅原因，此处不加赘述）。

​ 假设fac[x]代表 x! 在模p意义下的值，而inv(x)代表x在模p意义下的逆元，那么组合数C(m,n)在模p意义下的值就是fac[n] * inv(fac[m]) * inv(fac[n-m])。利用费马小定理求解组合数显得简单而快捷。

​ 但可能存在这么一种情况：若p是个较小的质数，此时整数x在模p意义下的逆元可能是不存在的（比如x是p的倍数），此时费马小定理就不再适用了。

​ 因此，我们不妨考虑进行分治，并引入Lucas定理求解：

假设p为质数，m<=n。

当m>n时，组合数C(m,n)无意义，设为0。

  • 当C(m,n)中的n位于(0,p-1]范围内，显然其逆元均是存在的，可利用费马小定理求解；

  • 当n >= p时，由Lucas同余式可知，C(m,n) = C(m/p,n/p) * C(m%p,n%p) %p。根据模除的性质，显然有m%p < p与n%p < p，均位于费马小定理适用的范围内，可利用费马小定理直接求解；

  • 随后分析C(m/p,n/p)。若仍有n/p >= p，显然可继续进行分治，过程同上。观察上述过程可知，最后必有m = 0，此时C(m,n) = 1，结束。

实际上，上述递归过程就是整数n,m进行p进制展开的过程（可以思考一下为什么）。并且可以很容易地得出其递归调用的次数为\(log_pm\)​​​。

若线性预处理p以内的阶乘和逆元，则C(m%p,n%p)的求解过程可视为O(1)。那么，算法的总复杂度为O(\(p+qlog_pm\))，其中q为询问次数。

​ 上述过程可写成如下代码形式（略去了线性预处理的过程）：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
typedef long long ll;
ll mpow(ll base,ll x,ll p){  //模p意义下的快速幂
    ll ans = 1;
    while(x){
        if(x&1)ans = ans*base%p;
        base = base*base%p;
        x >>= 1;
    }
    return ans;
}

inline ll C(ll m,ll n,ll p){  //模p意义下的组合数
    return n<m ? 0 : (fac[n] * inv[m])%p * inv[n-m] % p;
}
//注意上述inv[x]表示fac[x]的逆元而非自然数x的逆元

ll lucas(ll m,ll n,ll p){  //模p意义下的lucas函数
    return m == 0 ? 1 : lucas(m/p,n/p,p) * C(m%p,n%p,p) % p;
}

​ 以上即Lucas定理的简述，希望能对读者有所帮助。