Lucas

作者: burningrain | 来源:发表于2021-03-28 00:42 被阅读0次

    Lucas定理是用来求 C(n,m) \% pp为素数的值。(注意:p一定是素数)
    Lucas定理用来解决大组合数求模是很有用的。
    fac[]p决定
    p是C(n,m)\%p

    ll fac[10];
    ll p=3;
    void init(){
        fac[0]=1;
        for(ll i=1;i<p;i++)
            fac[i]=fac[i-1]*i%p; 
    }
    ll power(ll a,ll b,ll mod){
        ll ans=1;
        while(b){
            if(b&1) ans=(ans*a)%mod;
            a=(a*a)%mod;
            b>>=1;
        }
        return ans;
    }
    ll C(ll n,ll m){
        if(n<m)
            return 0;
        return fac[n]*power(fac[m]*fac[n-m],p-2,p)%p;
    }
    ll lucas(ll n,ll m){
        if(m==0)
            return 1;
        return (C(n%p,m%p)*lucas(n/p,m/p))%p;
    }
    

    相关文章

      网友评论

          本文标题:Lucas

          本文链接:https://www.haomeiwen.com/subject/wqbuhltx.html