NT/Combinatorics/Comb_common.hpp

• View this file on GitHub
• Last update: 2024-05-25 08:47:49+07:00
• Include: #include "NT/Combinatorics/Comb_common.hpp"

Verified with

• test/yosupo/Math/BC_prime_mod.test.cpp

Code

#pragma once
template<class T>
struct Comb {
    int n;
    vector<T> _fac;
    vector<T> _invfac;
    vector<T> _inv;

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

    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }

    T fac(int m) {
        if (m > n) init(m);
        return _fac[m];
    }

    T invfac(int m) {
        if (m > n) init(m);
        return _invfac[m];
    }

    T inv(int m) {
        if (m > n) init(m);
        return _inv[m];
    }

    T binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
};

#line 2 "NT/Combinatorics/Comb_common.hpp"
template<class T>
struct Comb {
    int n;
    vector<T> _fac;
    vector<T> _invfac;
    vector<T> _inv;

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

    void init(int m) {
        if (m <= n) return;
        _fac.resize(m + 1);
        _invfac.resize(m + 1);
        _inv.resize(m + 1);
        for (int i = n + 1; i <= m; i++) {
            _fac[i] = _fac[i - 1] * i;
        }
        _invfac[m] = _fac[m].inv();
        for (int i = m; i > n; i--) {
            _invfac[i - 1] = _invfac[i] * i;
            _inv[i] = _invfac[i] * _fac[i - 1];
        }
        n = m;
    }

    T fac(int m) {
        if (m > n) init(m);
        return _fac[m];
    }

    T invfac(int m) {
        if (m > n) init(m);
        return _invfac[m];
    }

    T inv(int m) {
        if (m > n) init(m);
        return _inv[m];
    }

    T binom(int n, int m) {
        if (n < m || m < 0) return 0;
        return fac(n) * invfac(m) * invfac(n - m);
    }
};

Back to top page