目录
什么是Lucas定理
证明Lucas定理
Lucas定理求解组合数的C++实现

什么是Lucas定理

这是一个有助于分解组合数来求解的定理，适合模数小，数字大的问题。

有质数 \(p\)，对于\(n,m\)，如果\(n=k_1p+b_1,m=k_2p+b_2\),有

\[C_n^m\equiv C_{k_1}^{k_2}C_{b_1}^{b_2} \pmod p
\]

由此可以分解成较小的问题求解。

证明Lucas定理

这个证明利用了二项式定理的思路，前所未闻，真的很有趣。

根据二项式定理可以得到 \((1+x)^n\)中\(x^m\)的系数为\(C_n^m\)。

我们用这一点作为突破口，对于\((1+x)^n\)，我们有

\[(1+x)^n\equiv (1+x)^{k_1p+b_1}\equiv (1+x)^{k_1p}(1+x)^{b_1}\equiv ((1+x)^p)^{k_1}(1+x)^{b_1}\pmod p
\]

然后有一个很有意思的东西

\[(1+x)^p\equiv 1+x^p \pmod p
\]

为什么呢？将式子拆开后，显然除了第一项与最后一项，其他项是\(p\)的倍数，自然就会抹掉了。

继续进行推导，我们有

\[(1+x)^n\equiv(1+x^p)^{k_1}(1+x)^{b_1}\pmod p
\]

于是右边的式子拆开可以得到

\[(\sum_{i=0}^{k_1} C_{k_1}^i x^{pi})(\sum_{j=0}^{b_1} C_{b_1}^j x^{j})\pmod p
\]

我们要求\(x^m\)的系数，也就是\(x^{k_2p+b_2}\)的系数。

由于\(b_1<p\),所以\(k_2p\)只能让\(\sum_{i=0}^{k_1} C_{k_1}^i x^{pi}\)负责了，当\(i=k_2\)时符合条件，此时系数为\(C_{k_1}^{k_2}\)。

剩下部分由\(\sum_{j=0}^{b_1} C_{b_1}^j x^{j}\)负责，当\(j=b_2\)时符合条件，此时系数为\(C_{b_1}^{b_2}\)。

因此 \(x^m\)的系数为\(C_{k_1}^{k_2}C_{b_1}^{b_2}\)，前文已知根据二项式定理\(x^m\)的系数为\(C_n^m\)，我们得到

\[C_n^m\equiv C_{k_1}^{k_2}C_{b_1}^{b_2} \pmod p
\]

由此，完成了Lucas定理的证明。

Lucas定理求解组合数的C++实现

代码上没什么难点，首先基础的组合数求解还是要有的，也就是我们需要预处理阶乘逆元，然后使用Lucas将组合数拆开再用基础的组合数求解即可。

long long ksm(long long x,long long y)

{

    long long sum=1;

    while(y)

    {

        if(y&1)

        {

            sum*=x;

            sum%=mod;

        }

        x*=x;

        x%=mod;

        y>>=1;

    }

    return sum;

}

long long C(long long n,long long m)

{

    if(m>n)return 0;

    if(m==0||n==m)return 1;

    return fac[n]*inv[m]%mod*inv[n-m]%mod;

}

long long lucas(long long n,long long m)

{

    if(m>n)return 0;

    if(n<mod)return C(n,m);

    return lucas(n/mod,m/mod)*lucas(n%mod,m%mod)%mod;

}

void init()

{

    fac[0]=1;

    for(int i=1;i<=mod-1;i++)

    {

        fac[i]=fac[i-1]*i%mod;

    }

    inv[mod-1]=ksm(fac[mod-1],mod-2);

    for(int i=mod-2;i>=0;i--)

    {

        inv[i]=inv[i+1]*(i+1)%mod;

    }

}

Lucas定理——定义、证明、实现、运用的相关教程结束。