Lucas定理学习笔记

Lucas定理：

\[{n\choose m}\equiv{\lfloor{\frac{n}{p}\rfloor}\choose \lfloor \frac{m}{p}\rfloor}\times{n\%p\choose m\%p} \mod p\]
此处的\(\%\)表示的是取模运算。

证明：

考虑化简\({n\choose m}=\frac{n!}{m!\times (n-m)!}\)，不难发现当n和m都远大于p的时候为了简化运算我们可以将n,m,(n-m)都给按照p分段，如果\(n\%p \geq m\%p\)，那么可以发现以分数线为界，分数线上面的整数段一定和分数线下面的整数段相同，反之则分数线上面的整数段比下面的整数段大1（这种情况不难发现答案是0）。
于是我们只考虑上面和下面整数段相同的情况，先计算剩下来的边角，根据同余可得边角料的部分为\({n\%p\choose m\%p}\)。
然后考虑对于这些整块，要如何简化运算。根据同余定理和逆元的一些性质可以得到对于分子和分母对于p同余且不是p的倍数的部分一定可以消掉，就像这样：
\[\frac{1\times 2\times \dots \times p\times (p+1)\times (p+2)\times \cdots \times (t\times p)}{1\times 2\times \cdots \times (b\times p)\times 1\times 2\cdots\times ((t-b)\times p)}\\\equiv\frac{p\times 2p\times \cdots \times tp}{p\times \cdots\times bp\times p\times (t-b)p} \mod p\]
然后我们把分子分母同时除以一个\(p^t\)，就可以得到这部分的值为\(\lfloor{\frac{n}{p}\rfloor}\choose \lfloor \frac{m}{p}\rfloor\)了。
最后可得\({n\choose m}\equiv{\lfloor{\frac{n}{p}\rfloor}\choose \lfloor \frac{m}{p}\rfloor}\times{n\%p\choose m\%p} \mod p\)。
证毕。
以上内容均为自己的对于Lucas定理及其证明的浅解，如有错误，欢迎指正。

#include<bits/stdc++.h>

#define REP(i,a,b) for(int i=a,i##_end_=b;i<=i##_end_;++i)
#define DREP(i,a,b) for(int i=a,i##_end_=b;i>=i##_end_;--i)
#define MREP(i,x) for(int i=beg[x],v;v=to[i],i;i=las[i])
#define debug(x) cout<<#x<<"="<<x<<endl
#define fi first
#define se second
#define mk make_pair
#define pb push_back
typedef long long ll;

using namespace std;

void File(){
    freopen("luogu3807.in","r",stdin);
    freopen("luogu3807.out","w",stdout);
}

template<typename T>void read(T &_){
    T __=0,mul=1; char ch=getchar();
    while(!isdigit(ch)){
        if(ch=='-')mul=-1;
        ch=getchar();
    }
    while(isdigit(ch))__=(__<<1)+(__<<3)+(ch^'0'),ch=getchar();
    _=__*mul;
}

const int maxn=1e5+10;
int T;
ll n,m,p,fac[maxn<<1];

ll qpow(ll x,ll y){
    ll ret=1; x%=p;
    while(y){
        if(y&1)ret=ret*x%p;
        x=x*x%p;
        y>>=1;
    }
    return ret;
}

ll calc(ll x,ll y){
    if(x<p && y<p){
        if(x<y)return 0;
        return fac[x]*qpow(fac[y],p-2)%p*qpow(fac[x-y],p-2)%p;
    }
    return calc(x/p,y/p)*calc(x%p,y%p)%p;
}

int main(){
//  File();
    fac[0]=1;
    read(T);
    while(T--){
        read(n),read(m),read(p);
        REP(i,1,n+m)fac[i]=fac[i-1]*i%p;
        printf("%lld\n",(calc(n+m,m)%p+p)%p);
    }
    return 0;
}

Lucas定理学习笔记

原文：https://www.cnblogs.com/ylsoi/p/9931788.html