数论13——组合数学——lucas 算法（模板0.5 ）

女爷i 2024-04-17 05:53 72阅读 0赞

对于求大数 组合数，并mod p（p是素数）可以用lucas算法+乘法逆元

p小打表

#include<bits/stdc++.h>
    #define ll long long
    using namespace std;
    const int maxn = 1e6;
    ll fac[maxn];
    
    void init(ll p)// 求阶乘打表
    { 
        fac[0] = 1;
        for(ll i = 1;i <= p;i++)fac[i] = fac[i-1]*i%p;
    }
    
    ll pow_mod(ll a, ll n, ll mod)// 逆元
    { 
        ll ans = 1;
        while(n)
        { 
            if(n%2)ans = ans*a%mod;
            a = a*a%mod;
            n/=2;
        }
    
        return ans;
    }
    
    ll C(ll n, ll m, ll p)
    { 
        if(n < m)return 0;
    
        return fac[n]*pow_mod(fac[m]*fac[n-m]%p, p-2, p);
    }
    
    ll Lucas(ll n, ll m, ll p)//C(n, m)
    { 
        return m?Lucas(n/p, m/p, p)*C(n%p, m%p, p)%p:1ll;
    }
    
    int main()
    { 
    
    
    }

p大，不达标

ll pow(ll a, ll b, ll m)
    { 
        ll ans = 1;
        a %= m;
        while(b)
        { 
            if(b & 1)ans = (ans % m) * (a % m) % m;
            b /= 2;
            a = (a % m) * (a % m) % m;
        }
        ans %= m;
        return ans;
    }
    ll inv(ll x, ll p)//x关于p的逆元，p为素数
    { 
        return pow(x, p - 2, p);
    }
    ll C(ll n, ll m, ll p)//组合数C(n, m) % p
    { 
        if(m > n)return 0;
        ll up = 1, down = 1;//分子分母;
        for(int i = n - m + 1; i <= n; i++)up = up * i % p;
        for(int i = 1; i <= m; i++)down = down * i % p;
        return up * inv(down, p) % p;
    }
    ll Lucas(ll n, ll m, ll p)
    { 
        if(m == 0)return 1;
        return C(n % p, m % p, p) * Lucas(n / p, m / p, p) % p;
    }

p大时， 不打表

#include<iostream>
    #define ll long long
    using namespace std;
    
    ll exgcd(ll a, ll b, ll &x, ll &y)// ax+by == gcd(a, b)
    { 
        ll res;
        if(b == 0)
        { 
            x = 1;
            y = 0;
            return a;
        }
        res = exgcd(b,a%b, x, y);
    
        ll tmp = y;
        y =  x- a/b*y;
        x = tmp;
        return res;
    }
    ll mod_reverse(ll a, ll mod)
    { 
        ll x, y, d;
        d = exgcd(a, mod, x, y);
    
        if(d == 1)
        { 
            /**大于 0 的通******/
            if(x%mod <= 0)return x%mod+mod;
            else return x%mod;
        }
        else return -1ll;//(long long)-1;
    
    }
    
    ll C(ll n, ll m, ll mod)
    { 
        if(n < m)return 0;
        m = min(m, n-m);
        ll res = 1;
    
        for(ll i = m; i >= 1; i--)
        { 
            res = (res*(n-i+1)%mod * mod_reverse(i%mod, mod)%mod)%mod;
        }
        return res;
    }
    ll Lucas(ll n, ll m, ll p)//C(n, m)
    { 
        return m?Lucas(n/p, m/p, p)*C(n%p, m%p, p)%p:1ll;
    }```