卢卡斯定理

卢卡斯定理

( ext{Lucas}) 定理

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

定义：

对于质数模数 (p) ，满足以下定理：

[dbinom{n}{m} mod{p}equiv dbinom{leftlfloor n/p ight floor}{leftlfloor m/p ight floor} imesdbinom{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;

令：在 (pmod 2) 时，(dbinom{n}{m}=[(n&m)==m])

扩展 ( ext{Lucas}) 定理

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

咕咕咕