卢卡斯定理

---

概述:

卢卡斯定理解决了这样一个问题: 求$C^m_n\ mod\ p$, 其中$p$为质数.

这里先直接给出结论, 十分简单也十分好实现:

$${sp+q \choose tp+r} \equiv {s \choose t}{q \choose r}(mod\ p)$$

其中$0 \leq q,r < p$

代码实现时直接取$s = \lfloor \frac{n}{p} \rfloor$, $t = \lfloor \frac{m}{p} \rfloor$, $q = n\ mod\ p$, $r = m\ mod\ p$. 然后暴力计算$q \choose r$, 递归处理$s \choose t$即可.

int fc(int n,int m,int p) { //暴力处理
    int a(1),b(1);
    for(int i(0);i<m;++i) {
        a = ((LL)a*(n-i))%p;
        b = ((LL)b*(i+1))%p;
    }
    return (LL)a*(LL)(inv(b,p))%p;
}

int lucas(int n,int m,int p) {
    if(m==0) {  //m=0结束递归
        return 1;
    }
    return (LL)(fc(n%p,m%p,p))*(LL)(lucas(n/p,m/p,p))%p;
}

证明:

首先证明当$0 < m < p$时, $p|{p \choose m}$:

将$p \choose m$展开, 有:

$$\frac{p \cdot (p-1) \cdot ... \cdot (p-m+1)} {1 \cdot 2 \cdot ... \cdot m}$$

由于$m < p$, 所以分号下面的项没有质因子$p$, 而上面有. 所以$p|{p \choose m}$.

然后构造一个$(1+x)^n$, 有:

$$\begin{aligned} (1+x)^n & = (1+x)^{sp+q} \\ & = ((1+x)^p)^s \cdot (1+x)^q \end{aligned}$$

由二项式定理, 有:

$$\begin{aligned} (1+x)^p & = 1 + \sum_{i=1}^{p-1} {p \choose i} x^i + x^p \\ & \equiv 1 + x^p(mod\ p) \end{aligned}$$

将该式代入上式, 有:

左边取$x^m$, 当$0 \leq q < p$时, 右侧两个二项式只能取$x^{tp}$和$x^r$, 有:

$${n \choose m}x^m \equiv {s \choose t}x^{tp} \cdot {q \choose r}x^r (mod\ p)$$

左右消去$x^m$, 即证得卢卡斯定理:

$${n \choose m} \equiv {s \choose t}{q \choose r}(mod\ p)$$