Lucas 定理是用来求 \(C^n_m\mod p\) 的。

定理

\[C^n_m\equiv C^{n\bmod p}_{m\bmod p}\times C^{n/p}_{m/p}\pmod p \]

证明

由二项式定理得 \(C_a^b\) 为 \((1+x)^a\) 中 \(x^b\) 的系数。

同理，对于方程 \((1+x)^{a_0}(1+x^p)^{a_1}(1+x^{p^2})^{a_3}\dots(1+x^{p^k})^{a_k}\bmod p\)：

  • \(C_{a_0}^{b_0}\) 即为 \((1+x)^{a_0}\) 中 \(x^{b_0}\) 的系数；
  • \(C_{a_1}^{b_1}\) 即为 \((1+x)^{a_1}\) 中 \(x^{b_1}\) 的系数；
  • \(C_{a_2}^{b_2}\) 即为 \((1+x)^{a_2}\) 中 \(x^{b_2}\) 的系数；
  • \(\vdots\)
  • \(C_{a_k}^{b_k}\) 即为 \((1+x)^{a_k}\) 中 \(x^{b_k}\) 的系数。

将 \(C_{a_0}^{b_0}x^{b_0}\)，\(C_{a_1}^{b_1}x^{b_1}\)，\(C_{a_2}^{b_2}x^{b_2}\)，\(\dots\)，\(C_{a_k}^{b_k}x^{b_k}\) 相乘得 \(C_{a_0}^{b_0}C_{a_1}^{b_1}C_{a_2}^{b_2}\dots C_{a_k}^{b_k}\times x^b\)。

\(b=b_kp^k+b_{k-1}p^{k-1}+b_{k-2}p^{k-2}+\dots+b_1p+b_0\Rightarrow C^n_m\equiv C^{n\bmod p}_{m\bmod p}\times C^{n/p}_{m/p}\pmod p\)

命题获证。

应用

开头不就说了是求组合数的嘛awa

因为卢卡斯定理可以把一个巨大的组合数给拆掉，所以利用这个性质就能够求出 \(C_m^n \bmod 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 \pmod p \]
\[C_m^n\equiv \prod_{i=0}C_{m_ip^i}^{n_ip_i}\pmod p \]

可快速幂，把 \(m\) 和 \(n\) 拆成 \(p\) 进制数，然后直接暴力。

比如模板题 P3807：

#include<iostream>
using namespace std;
const int N=100010;  //最大值
typedef long long ll;
ll a[N];
int p;
inline ll qpow(ll n,int k) //快速幂用来求逆元
{
    ll ans=1,base=n;
    while (k)
	{
        if(k&1) ans=ans*base%p;
        base=base*base%p;k>>=1;
    }
    return ans%p;
}
inline ll C(ll m,ll n)  //组合数，有除法用逆元
{
    if (m<n) return 0;
    if (m==n||!n) return 1;
    if (n==1) return m;
    return a[m]*qpow(a[n],p-2)%p*qpow(a[m-n],p-2)%p;
}

inline ll Lucas(ll m,ll n)  //Lucas 代入公式
{
    if (!n) return 1;
    return C(m%p,n%p)*Lucas(m/p,n/p)%p;
}
int main()
{
    int t;
    cin>>t;
    while (t--)  //多组数据
	{
        ll m,n;
        cin>>n>>m>>p;
        a[0]=1;
        for (int i=1;i<=p;i++) a[i]=(a[i-1]*i)%p;  //预处理阶乘用来求组合数
        cout<<Lucas(n+m,m)<<'\n';
    }
    return 0;
}