Lucas（卢卡斯）定理

定义

若 \(p\) 为质数，且\(a\ge b\ge1\)，则有：

\[C_{a}^{b}\equiv C_{a/p}^{b/p}\cdot C_{a (mod\,p)}^{b(mod\,p)}
\]

拆分a与b

按照 \(p\) 进制拆分 \(a\) 与 \(b\) ,设 \(a\) 与 \(b\) 是 \(k\) 位，不足用 \(0\) 补足。

\[\left\{\begin{aligned}
a&=a_0p^{0}+a_1p^{1}+\cdots+a_{k-1}p^{k-1}+a_kp^{k}\\
b&=b_0p^{0}+b_1p^{1}+\cdots+b_{k-1}p^{k-1}+b_kp^{k}
\end{aligned}\tag{1}
\right.
\]

证明\((1+x)^{p}\equiv1+x^p\,mod\,p\)

根据二项式定理有：

\[\begin{aligned}
(1+x)^p&=C_p^0x^0+C_p^1x^1+C_p^2x^2+\cdots+C_p^{p-1}x^{p-1}+C_p^px^p\\
&=1+C_p^1x+C_p^2x^2+\cdots+C_p^{p-1}x^{p-1}+x^p\\

\end{aligned}
\]

\(\because p为质数\therefore1\sim p-1均与p互质\\\therefore C_p^2,C_p^3,\cdots,C_p^{p-1}均能整除p,即C_p^2,C_p^3,\cdots,C_p^{p-1}\,mod\,p=0\)

\[(1+x)^p\equiv(1+x^p)\,mod\,p\tag{2}
\]

即 \((1+x)^p\) 在模 \(p\) 的意义下与 \((1+x^p)\) 同余。

根据 \((1+x)^a\) 求解 \(C_b^a\)

设 \(a=\lfloor \frac{a}{p}\rfloor p+a\%p\)，\(a’=\lfloor \frac{a}{p}\rfloor\) 有：

\[\begin{aligned}
(1+x)^a&=(1+x)^{\lfloor \frac{a}{p}\rfloor p+a\%p}\\
&=(1+x)^{a’p+a\%p}\\
&=(1+x)^{a’p}(1+x)^{a\%p}\\
\because a\%p=a_0
\therefore &=(1+x)^{a’p}(1+x)^{a_0}\\
&=\underline{((1+x)^p)^{a’}}(1+x)^{a_0}\\
\because公式(2)
\therefore &=\underline{(1+x^p)^{a’}(1+x)^{a_0}}
\end{aligned}\tag{3}
\]

再设 \(a’=\lfloor \frac{a’}{p}\rfloor p+a’\%p\)，\(a”=\lfloor \frac{a’}{p}\rfloor\) 有：

\[\begin{aligned}
((1+x)^p)^{a’}&=(1+x^p)^{\lfloor \frac{a’}{p}\rfloor p+a’\%p}\\
&=(1+x^p)^{a”p+a’\%p}\\
&=(1+x^p)^{a”p}((1+x)^p)^{a’\%p}\\
\because a’\%p=a_1
\therefore &=(1+x^p)^{a”p}((1+x)^p)^{a_1}\\
&=\underline{(1+x^p)^p)^{a”}((1+x)^p)^{a_1}}\\
\because公式(2)
\therefore &=\underline{(1+x^{p^2})^{a”}(1+x^p)^{a_1}}
\end{aligned}\tag{4}
\]

同理，可得到

\[(1+x^{p^2})^{a”}=(1+x^{p^3})^{a”’}\underline{(1+x^{p^2})^{a_2}}
\]

这样经过不断的迭代，最终得到:

\[(1+x)^a=(1+x^{p^k})^{a_k}*(1+x^{p^{k-1}})^{a_{k-1}}
*\cdots*(1+x^p)^{a_1}*(1+x)^{a_0}\tag{5}
\]

等式两边运用二项式分别求 \(C_a^bx^b\) ,右边可以看作 \(b\) 个球分到了 \(k\)个盒子里，每个盒子里面得数量就是 \(b_i(1\le i\le k)\) 得

\[\begin{aligned}
C_a^bx^b&=C_{a_k}^{b_k}x^{p^kb_k}C_{a_{k-1}}^{b_{k-1}}x^{p^{k-1}b_{k-1}}\cdots C_{a_1}^{b_1}x^{pb_1}C_{a_0}^{b_0}x^{b_0}\\
&=(\prod_{i=0}^k{C_{a_i}^{b_i}})(x^{\sum_{i=0}^{k}{p^ib_i}})\\
\because 公式(1)中b的展开式
\therefore &=(\prod_{i=0}^k{C_{a_i}^{b_i}})x^b\\
\end{aligned}
\]

等式两边同时消去 \(x^b\) ，得：

\[C_a^b\,mod\,p\equiv \prod_{i=0}^{k}{C_{a_i}^{b_i}}\tag{6}
\]

根据递归的过程，也可写成：

\[C_a^b\,mod\,p=C_{a/p}^{b/p}C_{a\%p}^{b\%p}\tag{7}
\]

代码：

下面以AcWing 887. 求组合数 III为例：传送门

使用 \(Lucas\) 定理主要使用公式\(7\)的递推式
函数int C(int a, int b)实现\(C_a^b\)的求解，使用\(C_a^b=\frac{a*(a-1)*\cdots*(a-b+1)}{b*(b-1)*\cdots*1}\),分子用逆元即可

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
typedef long long ll;
const int N = 100010;
int n;
int p;
int qmi(int a, int b) {
    int res=1;
    while(b) {
        if(b&1) res=(ll)res*a%p;
        a=(ll)a*a%p;
        b>>=1;
    }
    return res;
}
int C(int a, int b) {
    int res=1;
    for(int i=1,j=a;i<=b;++i,--j) {
        res=(ll)res*j%p;
        res=(ll)res*qmi(i,p-2)%p;
    }
    return res;
}
int lucas(ll a, ll b) {
    if(a<p&&b<p) return C(a,b);
    return (ll)C(a%p,b%p)*lucas(a/p,b/p)%p;
}
int main() {
    #ifdef ONLINE_JUDGE
    #else
    freopen("in.txt","r",stdin);
    freopen("out.txt","w",stdout);
    #endif // ONLINE_JUDGE
    scanf("%d",&n);
    while(n--) {
        ll a,b;
        scanf("%lld%lld%lld",&a,&b,&p);
        printf("%d\n",lucas(a,b));
    }
    return 0;
}