快速幂 && 求逆元 && 求组合数

快速幂 && 逆元 && 求组合数(模数固定，且a, b不大)

const LL mod = 998244353;

LL power(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

LL power(LL a, LL b, LL p) {
    LL res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

LL inv(LL x) {
    return power(x, mod - 2);
}

LL inv(LL x, LL p) {
    return power(x, p - 2, p);
}

struct Comb {
    LL n;
    std::vector<LL> _fac, _invfac, _inv;

    Comb() : n{0}, _fac{1}, _invfac{1}, _inv{0} {}
    Comb(LL n) : Comb() {
        init(n);
    }

    void init(LL m) {
        m = std::min(m, mod - 1);
        if (m <= n) {
            return ;
        }
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);

        for (LL i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i % mod;
        }

        _invfac[m] = inv(_fac[m]);
        for (LL i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i % mod;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }

        n = m;

    }

    LL get_fac(LL m) { // m的阶层
        if (m > n) {
            init(2 * m);
        }
        return _fac[m];
    }

    LL get_invfac(LL m) { // m的阶层的逆元
        if (m > n) {
            init(2 * m);
        }
        return _invfac[m];
    }

    LL get_inv(LL m) { // m的逆元
        if (m > n) {
            init(2 * m);
        }
        return _inv[m];
    }

    LL binom(LL n, LL m) { // C(n, m);
        if (n < m || m < 0) {
            return 0;
        }
        LL res = get_fac(n) * get_invfac(m) % mod * get_invfac(n - m) % mod;
        return res;
    }

} comb;

lucas求组合数

时间复杂度与模数相关

适用于模数不同且中很大的情况

const LL mod = 998244353;

LL power(LL a, LL b) {
    LL res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % mod;
        }
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

LL power(LL a, LL b, LL p) {
    LL res = 1;
    while (b) {
        if (b & 1) {
            res = res * a % p;
        }
        a = a * a % p;
        b >>= 1;
    }
    return res;
}

LL inv(LL x) {
    return power(x, mod - 2);
}

LL inv(LL x, LL p) {
    return power(x, p - 2, p);
}

LL C(LL a, LL b, LL p) {
    if (a < b) {
        return 0;
    }
    LL res = 1;
    for (int i = 1, j = a; i <= b; i++, j--) {
        res = res * j % p;
        res = res * inv(i, p) % p;
    }
    return res;
}

LL lucas(LL a, LL b, LL p) {
    if (a < p && b < p) {
        return C(a, b, p);
    }
    return C(a % p, b % p, p) * lucas(a / p, b / p, p) % p;
}