C/C++教程

Lucas定理

本文主要是介绍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定理的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航