卢卡斯定理

发表于 分类于 ，

概述:

卢卡斯定理解决了这样一个问题：求 \(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\) 即可.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
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) \]