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定理的文章就介绍到这儿,希望我们推荐的文章对大家有所帮助,也希望大家多多支持为之网!