卢卡斯定理

· · 题解

以下的部分内容参考命题人讲座系列《初等数论》一书

本篇笔记具体介绍卢卡斯定理的内容,证明,性质以及在\texttt{OI}中的用途,如有错误和疑问,请在评论区写下您的意见.

内容

《初等数论》一书对卢卡斯\texttt{(Lucas)}定理是这么定义的:

设p为素数,a,b\in N^* ,并且

a=\sum\limits_{i=0}^k a_i p^i,b=\sum\limits_{i=0}^k b_i p^i

这里0\leqslant a_i,b_i\leqslant p-1都是整数,i=0,1,2,…,k.则:

C_a^b \equiv \prod\limits_{i=0}^k C_{a_i}^{b_i} \pmod{p}

或者写成这样:

C_a^b \equiv C_{a_k}^{b_k} \cdot C_{a_{k-1}}^{b_{k-1}} \cdot … \cdot C_{a_0}^{b_0}\pmod{p} Ps.$如果$b_i>a_i,$那么$C_{a_i}^{b_i} = 0 .

证明

该书对定理的证明运用到了生成函数的知识,如果不了解生成函数的话,可以上网查一下,证明如下:

引入多项式同余.设

f(x)=\sum\limits_{i=0}^n a_i x^i,g(x)=\sum\limits_{i=0}^n b_i x^i

是两个整系数多项式,如果对于0 \leqslant i \leqslant n,都有a_i \equiv b_i \pmod{m},那我们称这两个多项式对模m同余,即f(x) \equiv g(x) \pmod{m}.
显然我们知道对于k \in N,无论x取何值,必定有f(k) \equiv g(k) \pmod{m}.
下面我们要证明一个引理:

(1+x)^p \equiv 1+x^p \pmod{p}

考虑将左边利用二项式定理展开,并利用C_n^m=\frac{n}{m} C_{n-1}^{m-1},则易得C_p^1x到C_p^{p-1}x^{p-1}的部分分别模p余0,剩下的就是右边了.

利用该引理，我们可知

(1+x)^a = \prod\limits_{i=0}^k ((1+x)^{p^i})^{a_i} \qquad\quad\qquad\qquad\qquad\quad \equiv \prod\limits_{i=0}^k (1+x^{p^i})^{a_i} \pmod{p}.\quad (1)

然后对比两边x^b项系数即可.

书上给的证明中没有详细讲如何对比x^b项的系数,这里讲一下:

对于一个数,我们易知它在某某进制下只有一种表示,即对于

b=\sum\limits_{i=0}^k b_i p^i,

从b_0到b_n是确定的,那么对于(1)式右边,我们便有唯一确定的取法凑出x^b项,即在a_0中取b_0,在a_1中取b_1,以此类推……
在(1+x)^{a_0}中x^{b_0}项系数为C_{a_0}^{b_0},
在((1+x)^p)^{a_1}中x^{b_1 p}项系数为C_{a_1}^{b_1},

……

在((1+x)^{p^n})^{a_n}中x^{b_n p^n}项系数为C_{a_n}^{b_n},
又b=\sum\limits_{i=0}^k b_i p^i,
所以将上面的乘起来就是右边所算的x^b的系数,由多项式同余的定义,可知定理成立.

性质

该书又介绍了\texttt{Lucas}定理的两个性质:

  • 当且仅当存在i \in \{ 0, 1, 2, …,k\}使得b_i > a_i时,C_a^b \equiv 0 \pmod{p}.
  • C_a^b$ 为奇数的充要条件为二进制表示下$a$的每一位上的数都不小于$b$相应位上的数$.

应用

既然我们都把这东西都证出来了,那它有啥用呢?

作为一名曾经的\texttt{oier},当然要以实用为主啦.

\texttt{Lucas}$定理的主要用途在于在$O(\log_p a)$的时间求出$C_a^b \mod p$的结果$.$显然地$,$有一种方法$:

对于a,我们预处理出a_0,a_1,…,a_k,对于b同理.然后我们直接算组合数并乘起来,注意随时取模.如果p较小且询问较多,可以考虑预处理组合数.

这听起来很容易,但做起来好难啊.
这时候我们把秦九韶请出来,可以将

\sum\limits_{i=0}^k a_i p^i

变成

(((a_kp+a_{k-1})p+a_{k-2})p+…)p+a_0

这样的形式,对于另一个同理,于是我们便可以层层除法+取模,将求解变成了一个递归形式,即:

Lucas(a,b,p)=Lucas(a/p,b/p,p) \cdot C_{a\%p}^{b\%p},

这里的Lucas(a,b,p)即要求的C_a^b \mod p ,
代码如下:

#include<iostream>
using namespace std;
const int maxn=100010;
long long mul[maxn];
long long quickpow(long long a,long long b,long long c)
{
    long long ans=1;a=a%c;
    while(b)
    {
        if(b&1) ans=(ans*a)%c;
        b>>=1;a=(a*a)%c;
    }
    return ans;
}
long long c(long long n,long long m,long long p)
{
    return (m>n)?0:((mul[n]*quickpow(mul[m],p-2,p))%p*quickpow(mul[n-m],p-2,p)%p);
}
long long lucas(long long n,long long m,long long p)
{
    return (m==0)?1:c(n%p,m%p,p)*lucas(n/p,m/p,p)%p;
}
int main()
{
    int t;cin>>t;
    for(int i=1;i<=t;i++)
    {
        long long n,m,p;cin>>n>>m>>p;mul[0]=1;
        for(int i=1;i<=p;i++) mul[i]=(mul[i-1]*i)%p;        //预处理阶乘
        cout<<lucas(n+m,n,p)<<endl;
    }
    return 0;
}

这里的代码运用了费马小定理求阶乘逆元以及直接计算组合数,如果不了解逆元,请左转模板区(逃

例题的话,那就:
P3807 【模板】卢卡斯定理
P4345 [SHOI2015]超能粒子炮·改