摘要: 求组合数的代码模板和例题

【对算法，数学，计算机感兴趣的同学，欢迎关注我哈，阅读更多原创文章】
我的网站：潮汐朝夕的生活实验室
我的公众号：算法题刷刷
我的知乎：潮汐朝夕
我的github：FennelDumplings
我的leetcode：FennelDumplings

---

卢卡斯定理是由法国数学家爱德华·卢卡斯在1878年提出的，涉及到组合数和模运算，广泛应用于组合数学和数论中。

卢卡斯定理

设 p 是一个素数，将 m 和 n 写成 p 进制数：

$$n = a_{0} + a_{1}p + a_{2}p^{2} + \cdots + a_{k}p^{k} \\ m = b_{0} + b_{1}p + b_{2}p^{2} + \cdots + b_{k}p^{k} \\$$

其中：$0 \leq a_{i}, b_{i} < p (i=0,1,\cdots,k)$，则：

$$\binom{n}{m} \equiv \prod\limits_{i=0}\limits^{k}\binom{a_{i}}{b_{i}} \mod{p}$$

证明：二项式定理+比较系数

注意到 $1 \leq j \leq p^{i} - 1, i \geq 1$ 时，$\binom{p^{i}}{j}$ 是 $p$ 的倍数，故：

$$(1 + x)^{p^{i}} = 1 + x^{p^{i}} + \sum\limits_{j=1}\limits^{p^{i}-1}\binom{p^{i}}{j}x^{j} \equiv 1 + x^{p^{i}} \mod{p}$$

而上式在 $i=0$ 时，显然成立。因此：

$$\begin{align} (1+x)^{n} &= (1 + x)^{\sum\limits_{i=0}\limits^{k}a_{i}p^{i}} \\ &= \prod\limits_{i=0}\limits^{k}((1+x)^{p^{i}})^{a_{i}} \\ &\equiv \prod\limits_{i=0}\limits^{k}(1+x^{p^{i}})^{a_{i}} \mod{p} \\ &= \prod\limits_{i=0}\limits^{k}(\sum\limits_{j_{i}=0}\limits^{a_{i}}x^{p^{i}j_{i}}\binom{a_{i}}{j_{i}}) \mod{p} \\ \end{align}$$

上式左边 $x^{m}$ 的系数为 $\binom{n}{m}$

注意到 $m$ 表示成 p 进制数的唯一性，由 $m = \sum\limits_{i=0}\limits^{k}b_{i}p^{i}$，得上式右端 $x^{m}$ 的系数为：

$$\prod\limits_{i=0}\limits^{k}\binom{a_{i}}{b_{i}} \mod{p}$$

因此：

$$\binom{n}{m} \equiv \prod\limits_{i=0}\limits^{k}\binom{a_{i}}{b_{i}} \mod{p}$$

卢卡斯定理推论

令 $n = sp + q$，$m = tp + r$，$(q, r \leq p)$，则：

$$\binom{n}{m} \equiv \binom{s}{t}\binom{q}{r} \mod{p}$$

证明

将 n, m 用 p 进制数表示，如下：

$$\begin{align} n &= a_{0} + a_{1}p + a_{2}p^{2} + \cdots + a_{k}p^{k} \\ m &= b_{0} + b_{1}p + b_{2}p^{2} + \cdots + b_{k}p^{k} \\ \end{align}$$

由卢卡斯定理：

$$\binom{n}{m} \equiv \prod\limits_{i=0}\limits^{k}\binom{a_{i}}{b_{i}} \mod{p}$$

对比 $n = sp + q$，$m = tp + r$ 及其 p 进制表示，有：

$$q = a_{0} \\ r = b_{0} \\ s = a_{1} + a_{2}p + \cdots + a_{k}p^{k - 1} \\ t = b_{1} + b_{2}p + \cdots + b_{k}p^{k - 1} \\$$

由卢卡斯定理：

$$\binom{s}{t} \equiv \prod\limits_{i=1}\limits^{k}\binom{a_{i}}{b_{i}} \mod{p}$$

于是：

$$\binom{n}{m} \equiv \binom{s}{t}\binom{q}{r} \mod{p}$$

求大组合数模质数

如果要算 $\binom{n}{m}\mod{p}$，则可以用卢卡斯定理。

记 $Lucas(n, m, p) = \binom{n}{m}\mod{p}$，$n = sp + q$, $m = tp + r$，由卢卡斯定理的推论，公式如下：

$$\begin{align} Lucas(n, m, p) &= \binom{q}{r}Lucas(s, t, p) \\ &= \binom{n\mod{p}}{m\mod{p}}Lucas(\frac{n}{p}, \frac{m}{p}, p) \\ \end{align}$$

代码模板 (C++)

涉及到模下组合数、模下快速幂。

// 卢卡斯定理模板
// Lucas 定理实现 C(n,m) % p 的代码：
using ll = long long;
ll exp_mod(ll a, ll b, ll p)
{
    //快速幂取模
    ll res = 1;
    while(b != 0)
    {
        if(b & 1) res = (res * a) % p;
        a = (a * a) % p;
        b >>= 1;
    }
    return res;
}

ll Comb(ll a, ll b, ll p)
{
    //求组合数C(a,b) % p
    if(a < b)   return 0;
    if(a == b)  return 1;
    if(b > a - b)   b = a - b;

    ll ans = 1, ca = 1, cb = 1;
    for(ll i = 0; i < b; ++i)
    {
        ca = (ca * (a - i)) % p;
        cb = (cb * (b - i)) % p;
    }
    ans = (ca * exp_mod(cb, p - 2, p)) % p;
    return ans;
}

ll Lucas(ll n, ll m, ll p)
{
    //Lucas定理求C(n,m)%p
    ll ans = 1;

    while(n && m && ans)
    {
        ans = (ans * Comb(n % p, m % p, p)) % p;
        n /= p;
        m /= p;
    }
    return ans;
}

关于卢卡斯定理的例题，以及与预处理结合的用法，参考文章 组合数。

---