题解：P3807 【模板】卢卡斯定理/Lucas 定理

· · 题解

二项式定理

若 n 是正整数，则有：\begin{aligned} (x+y)^n = \sum_{i=0}^n C_{n}^{i} x^i y^{n-i} \end{aligned}。

用数学归纳法证明：

当 n=1 时原式显然成立。

假设 n=k 时原式成立，则 n=k+1 时，有：

\begin{aligned} (x+y)^{k+1} &= (x+y)(x+y)^k \\ &=(x+y) \sum_{i=0}^{k}C_{k}^{i} x^i y^{k-i} \\ &=(x+y) (C_k^0 y^k+C_k^1 x y^{k-1}+\dots+C_k^{k-1}x^{k-1}y+C_k^k x^k) \\ &=x^{k+1} + y^{k+1} + (C_k^0+C_k^1)xy^k+(C_k^1+C_k^2)x^2y^{k-1}+\dots+(C_k^{k-1}+C_k^k)x^ky \\ &= x^{k+1} + y^{k+1} + \sum_{i=1}^k (C_k^{i-1}+C_k^{i})x^i y^{k-i+1} \end{aligned}

因为

\begin{aligned} C_k^{i-1}+C_k^{i} &= \frac{k!}{(i-1)!(k-i+1)!} +\frac{k!}{i!(k-i)!} \\ &= \frac{k!\:i!\:(k-i)!+k!\:(i-1)!\:(k-i+1)!}{i! \: (i-1)! \: (k-i)! \: (k-i+1)!} \\ &= \frac{(k+1)!}{i! (k-i+1)!} \\ &= C_{k+1}^i \end{aligned}

所以

\begin{aligned} (x+y)^{k+1} &= x^{k+1} + y^{k+1} + \sum_{i=1}^k C_{k+1}^ix^i y^{k-i+1} \\ &=\sum_{i=0}^{k+1}C_{k+1}^ix^i y^{k-i+1} \end{aligned}

因此 n=k+1 时原式也成立，得证。

一个引理

若 p 是素数，则有：(x+y)^p \equiv x^p + y^p \pmod p。

证明：由二项式定理可知：\begin{aligned} (x+y)^p = \sum_{i=0}^p C_{p}^{i} x^i y^{p-i} \end{aligned}。

其中当 1 \le i < p 时：

\begin{aligned} C_p^i &= \frac{p!}{i!(p-i)!} \\ &= \frac{p\times(p-1)!}{i \times (i-1)!(p-i)!} \\ &= \frac{p}{i} C_{p-1}^{i-1} \end{aligned}

所以

\begin{aligned} C_p^i & \equiv \frac{p}{i} C_{p-1}^{i-1} \\ & \equiv \frac{p}{i} C_{p-1}^{i-1} \times i \times inv(i)\\ & \equiv p \times inv(i) C_{p-1}^{i-1} \\ & \equiv 0 \pmod p \end{aligned}

其中 inv(i) 表示 i 在模 p 意义下的乘法逆元。因为 p 是素数且 i < p，故 inv(i) 一定存在。

原式在同余式中只剩下 i=0,p 两项，得证。

Lucas 定理

若 p 是素数，则有：C_n^m \equiv C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \times C_{n \bmod p}^{m \bmod p} \pmod p 。

证明：

根据带余除法，令 n=ap+b,m=cp+d，其中 0 \le b,d < p。

根据二项式定理得到式子一：

(1+x) ^n \equiv \sum_{i=0}^{n} C_n^i x^i \pmod p

根据二项式定理和引理得到式子二：

\begin{aligned} (1+x) ^n &\equiv (1+x)^{ap+b} \\ &\equiv ((1+x)^p)^a\times(1+x)^b\\ &\equiv (1+x^p)^a \times(1+x)^b \\ &\equiv (\sum_{i=0}^a C_a^i x^{ip})(\sum_{j=0}^b C_b^j x^j) \pmod p \end{aligned}

由式子一可知 x^m 的系数为 C_n^m。

由式子二可知 x^m=x^{cp+d} 的系数为 C_a^c C_b^d。

因为 \lfloor \frac{n}{p} \rfloor = a ,\lfloor \frac{m}{p} \rfloor = c,n \bmod p =b,m \bmod p=d。

所以 C_n^m \equiv C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \times C_{n \bmod p}^{m \bmod p} \pmod p，证毕。

我们发现在求 C_n^m \bmod p 时不太好求，因为是两个很大的数相除，得转换成乘的形式。

因为 p 是素数，根据费马小定理：m!^{p-1} \equiv 1 \pmod p,(n-m)!^{p-1} \pmod p。

那么有：

C_n^m=\frac{n!}{m!(n-m)!} \equiv n! \times m!^{p-2} \times (n-m)!^{p-2} \pmod p

但是这样求是有一点问题的，因为 m! 或者 (n-m)! 可能是 p 的倍数，就不能用费马小定理了。

其实具体实现是可以避免的，因为在求 C_{n \bmod p}^{m \bmod p} \pmod p 时费马小定理是肯定成立的，可以直接求。 C_{\lfloor \frac{n}{p} \rfloor}^{\lfloor \frac{m}{p} \rfloor} \pmod p 虽然没法直接求，但是可以利用 Lucas 定理进一步拆开，直到都能够拆成可求解的形式即可。

Code

#include <stdio.h>
#define int long long
int f[100005];
void init(int a,int p){ //求阶乘，f[i]=i!
    f[0]=f[1]=1;
    for(int i=2;i<=a;++i)
        f[i]=(f[i-1]*i)%p;
}
int pow(int a,int b,int p){  //快速幂
    a%=p;
    int res=1;
    while(b>0){
        if(b&1ll) res=(res*a)%p;
        a=(a*a)%p;
        b>>=1ll;
    }
    return res;
}
int C(int m,int n,int p){
    if(m>n) return 0;
    return (f[n]*pow(f[m],p-2,p)%p *pow(f[n-m],p-2,p))%p; //利用费马小定理求C
}
int Lucas(int m,int n,int p){
    if(!m) return 1;
    return C(m%p,n%p,p)*Lucas(m/p,n/p,p)%p;
  //m%p、n%p时可以直接求，m/p、n/p时可能不满足费马小定理则继续递归拆解
}
signed main(){
    int T; scanf("%lld",&T);
    while(T--){
        int n,m,p; scanf("%lld%lld%lld",&n,&m,&p);
        init(n+m,p);
        printf("%lld\n",Lucas(n,n+m,p));
    }
}