卢卡斯定理

卢卡斯定理

\(\text{Lucas}\) 定理

P3807 【模板】卢卡斯定理/Lucas 定理

定义:

对于质数模数 \(p\) ,满足以下定理:

\[\dbinom{n}{m} \mod{p}\equiv \dbinom{\left\lfloor n/p\right\rfloor}{\left\lfloor m/p\right\rfloor}\times\dbinom{n\%p}{m\%p}\mod{p} \]

最终 \(\dbinom{n}{m}\) 中的 \(n<p,m<p\) ,可以通过 \(\dbinom{n}{m}=\dfrac{n!}{m!(n-m)!}\) 算出(记得算逆元)。

\(p\) 的范围可以再 \(10^5\) 以内。

复杂度:\(O(\log^2{n})\)

主要代码:

ll C(ll n,ll m,ll p)
{
	 if(n<m) return 0;
	 return mi[n]*Pow(mi[m],p-2,p)%p*Pow(mi[n-m],p-2,p)%p;
}
ll Lucas(ll n,ll m,ll p)
{
	 if(m==0) return 1ll;
	 else return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;
}

mi[0]=1;
for(int i=1;i<=p;i++) mi[i]=mi[i-1]*i%mod;

扩展 \(\text{Lucas}\) 定理

对于任意模数 \(p\) (可以不是质数)

咕咕咕

上一篇:【Coel.学习笔记】卢卡斯定理(Lucas Theorem)


下一篇:Saving Beans HDU - 3037(卢卡斯定理)