To boldly go where no one has gone before.

【学习笔记】卢卡斯定理

2019-04-02 13:55:51


卢卡斯定理是用于求$C_m^n\mod p$的一种算法。

定理

$$C_m^n\equiv C_{m\mod p}^{n\mod p}\times C_{m/p}^{n/p}(\mod p)$$

推导

首先,对于$C_m^n$有:$$C_m^n=\frac{m!}{n!(m-n)!}=\frac{m}{n}\cdot\frac{(m-1)!}{(n-1)!(m-n)!}=\frac mn\cdot C_{m-1}^{n-1}$$ 由二项式定理:$$(a+b)^n=\sum_{i=0}^nC_n^ia^{n-i}b^i$$ 因此可知:$$(1+x)^p\equiv \sum_{i=0}^p C_p^ix^i\equiv C_p^01^px^0+C_p^p1^0x^p\equiv 1+x^p(\mod p)$$ 取首尾两式整理得:$$(1+x)^p\equiv 1+x^p(\mod p)$$ 由这个性质,设$m=k_1p+r_1,n=k_2p+r_2$,有:$$C_m^n\equiv C_{k_1p}^{k_2p}\cdot C_{r_1}^{r_2}(\mod p)$$ 所以从一个二项式开始展开:$$(1+x)^m=(1+x)^{k_1p+r_1}=(1+x)^{k_1p}\cdot(1+x)^{r_1}$$$$\because (1+x)^{k_1p}\equiv((1+x)^p)^{k_1}\equiv(1+x^p)^{k_1}(\mod p)$$$$\therefore (1+x)^n\equiv (1+x^p)^{k_1}\cdot(1+x)^{r_1}(\mod p)$$ 找到$x^n$项:$$\because C_m^nx^n\equiv (C_{k_1}^{k_2}\cdot x^{k_2p})( C_{r_1}^{r_2}\cdot x^{r_2})\equiv C_{k_1}^{k_2}\cdot C_{r_1}^{r_2}x^n (\mod p)$$$$\therefore \text{约掉}x^n\text{可得:}C_m^n\equiv C_{k_1}^{k_2}\cdot C_{r_1}^{r_2}$$

应用

因为卢卡斯定理可以把一个巨大的组合数给拆掉,所以利用这个性质就能够求出$C_m^n \mod p$,也就是说:$$C_m^n\equiv C_{m_0}^{n_0}\cdot C_{m_1p}^{n_1p}\cdot C_{m_2p^2}^{n_2p^2}\cdots (\mod p)$$$$C_m^n\equiv \prod_{i=0}C_{m_ip^i}^{n_ip_i}(\mod p)$$ 可联想到快速幂,先把$m$和$n$拆成$p$进制数,然后直接暴力计算就可以了。

模板 P3807

注意: 题目要求的是$C_{n+m}^m\mod p$,所以输入的时候稍微不太一样。

可以留意如何将一个数拆成$p$进制数,操作较为高级。


代码

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 100010;
long long a[MAXN];
int p;

inline long long Pow(long long base, int k) {
    long long res = 1;
    base %= p;
    for(register int i = k; i; i >>= 1) {
        if(i & 1)
            res = res * base % p;
        base = base * base % p;
    }
    return res % p;
}

inline long long C(long long m, long long n) {
    if(m < n)
        return 0;
    if(m == n || n == 0)
        return 1;
    if(n == 1)
        return m;
    return a[m] * Pow(a[n], p-2) % p * Pow(a[m-n], p-2) % p;
}

inline long long Lucas(long long m, long long n) {
    if(!n)
        return 1;
    return C(m % p, n % p) * Lucas(m/p, n/p) % p;
}

int main() {
    int t;
    scanf("%d", &t);
    while(t--) {
        long long m, n;
        scanf("%lli%lli%lli", &n, &m, &p);
        a[0] = 1;
        for(register int i = 1; i <= p; i++)
            a[i] = (a[i-1] * i) % p;
        printf("%lli\n", Lucas(n + m, m));
    }
    return 0;
}