脚本宝典收集整理的这篇文章主要介绍了Lucas定理，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

若P为质数，则对于任意整数1<=m<=n，有： C (n,m) = C (n%p, m%p) • C (n/p, m/p) (mod p) 相当于把n, m表示成p进制数，对P进制每一位计算组合数再相乘

时间复杂度：O()

ll ksm(ll a,ll b){...}

ll C(ll n,ll m)
{
    if(m>n) return 0;
    ll a=1,b=1;
    if(m>n-m) m=n-m;//C(n,m)=C(n,n-m)
    for(int i=1;i<=m;++i){
       a=a*(n-i)%mod;//(n!/(n-m)!)%mod
       b=b*i%mod;//(m!)%mod
    }
    return a*ksm(b,mod-2)%mod；//费马小定理
}

ll lucas(ll n,ll m)
{return !m||n==m?1:C(n%mod,m%mod)*lucas(n/mod,m/mod)%mod;}

脚本宝典总结

以上是脚本宝典为你收集整理的Lucas定理全部内容，希望文章能够帮你解决Lucas定理所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。