Lucas 定理 及扩展Lucas 学习笔记

Lucas 定理：

解决问题：

求

\[C_n^m\bmod k\]

内容：

\[C_n^m\equiv C_{n/p}^{m/p}*C_{n\bmod p}^{m\bmod p}\]

证明：

因为wyh很懒为方便写作，以下的 = 都是mod p 意义下的同余,/都是整除（即向下取整）

对于任意质数\(p\)，有

\[(1+x)^p= 1+x^p\]

由费马小定理得：

\[(1+x)^p= 1+x^p=1+x\]

设：

\[a=n/p,b=m/p\]
\[c=n\bmod p,d=m\bmod p\]

即：

\[n=ap+c\]
\[m=bp+d\]

现在推一波柿子：

\[(1+x)^n=(1+x)^{n/p*p}(1+x)^b\]
\[=(1+x^p)^{n/p}(1+x)^b\]
\[=\sum_{i=0}^kC_{n/p}^{i}x^{pj}\sum_{j=0}^kC_b^jx^j\]

前方高能！这里有一种很巧妙的想法反正wyh认为自己的智商是想不到的qwq：考虑这个等式两边\(m^x\)的系数

等式左边：

\[C_n^m\]

等式右边：

\[C_{n/p}^i*C_b^j,(pi+j=m,j<p)\]
\[=C_{n/p}^{m/p}*C_b^d\]

所以：

\[C_n^m\equiv C_{n/p}^{m/p}*C_{n\bmod p}^{m\bmod p}\]

Code

inline ll C(ll n,ll m)
{
    if(n<m) return 0;
    m=min(m,n-m);
    ll x1=1,x2=1;
    for(int i=n-m+1;i<=n;++i) x1=x1*i%p;
    for(int i=1;i<=m;++i) x2=x2*i%p;
    return x1*inv(x2)%p;
}

inline ll lucas(ll n,ll m)
{
    if(!m) return 1;
    return C(n%p,m%p)*lucas(n/p,m/p)%p;
}

Lucas 定理 及扩展Lucas 学习笔记

原文：https://www.cnblogs.com/oierwyh/p/11396879.html