Enumeration
(Math/Enumeration.hpp)

• View this file on GitHub
• Last update: 2022-07-30 23:47:06+09:00
• Include: #include "Math/Enumeration.hpp"

組み合わせ Modintを乗せる想定

コンストラクタ

Enumeration<Mint> enu;

fact, finv, inv配列を作成.

計算量

• $O(1)$

fact

Mint enu.fact(int n)

$n!$を求める.

計算量

• updateされていない場合、nまでupdateを行う。
• それ以降は$O(1)$

finv

Mint enu.finv(int n)

$(n!)^{-1}$を求める.

計算量

• updateされていない場合, nまでupdateを行う.
• それ以降は$O(1)$

inv

Mint enu.inv(int n)

$n^{-1}$を求める.

計算量

• updateされていない場合, nまでupdateを行う.
• それ以降は$O(1)$

nPk

Mint enu.nPk(int n, int k)

${}_nP_k$を求める. $k < 0$または$n < k$の場合, $0$を返す.

計算量

• updateされていない場合, nまでupdateを行う.
• それ以降は$O(1)$

nCk

Mint enu.nCk(int n, int k)

${}_nC_k$を求める. $k < 0$または$n < k$の場合, $0$を返す.

計算量

• updateされていない場合, nまでupdateを行う.
• それ以降は$O(1)$

nHk

Mint enu.nHk(int n, int k)

${}_nH_k$を求める. $k < 0$または$n < 0$の場合, $0$を返す.

計算量

• updateされていない場合, n+k-1までupdateを行う.
• それ以降は$O(1)$

Catalan

Mint enu.Catalan(int n)

カタラン数${}{2n}C_n-{}{2n}C_{n-1}$ を計算する．これは，$n$個の()の正しい括弧列の個数に一致する。 本質は$c_n+1 = \sum_{i=0}^{n} c_i c_{n-i}$ この漸化式を解いたものがカタラン数となる。

計算量

• updateされていない場合, 2nまでupdateを行う.
• それ以降は$O(1)$

Verified with

• Test/aoj-DPL-5-B.test.cpp

Code

template<class T> struct Enumeration{
  public:
    Enumeration(int sz = 0) { update(sz); }

    T fact(int k) {
        update(k);
        return _fact[k];
    }

    T finv(int k) {
        update(k);
        return _finv[k];
    }

    T inv(int k) {
        update(k);
        return _inv[k];
    }

    T nPk(int n, int k) {
        if(k < 0 || n < k) return 0;
        return fact(n) * finv(n - k);
    }

    T nCk(int n, int k) {
        if(k < 0 || n < k) return 0;
        return fact(n) * finv(k) * finv(n - k);
    }

    T nHk(int n, int k) {
        if(n < 0 || k < 0) return 0;
        if(n == 0) return 1;
        else return nCk(n + k - 1, k);
    }

    T Catalan(int n){
        return nCk(2*n, n) - nCk(2*n, n-1);
    }

  private:
    vector<T> _fact, _finv, _inv;

    void update(int sz) {
        if(_fact.size() < sz + 1){
            int pre_sz = max(1, (int)_fact.size());
            _fact.resize(sz + 1, T(1));
            _finv.resize(sz + 1, T(1));
            _inv.resize(sz + 1, T(1));
            for(int i = pre_sz; i <= (int)sz; i++) {
                _fact[i] = _fact[i - 1] * T(i);
            }
            _finv[sz] = T(1) / _fact[sz];
            for(int i = (int)sz - 1; i >= pre_sz; i--) {
                _finv[i] = _finv[i + 1] * T(i + 1);
            }
            for(int i = pre_sz; i <= (int)sz; i++) {
                _inv[i] = _finv[i] * _fact[i - 1];
            }
        }
    }

};

#line 1 "Math/Enumeration.hpp"
template<class T> struct Enumeration{
  public:
    Enumeration(int sz = 0) { update(sz); }

    T fact(int k) {
        update(k);
        return _fact[k];
    }

    T finv(int k) {
        update(k);
        return _finv[k];
    }

    T inv(int k) {
        update(k);
        return _inv[k];
    }

    T nPk(int n, int k) {
        if(k < 0 || n < k) return 0;
        return fact(n) * finv(n - k);
    }

    T nCk(int n, int k) {
        if(k < 0 || n < k) return 0;
        return fact(n) * finv(k) * finv(n - k);
    }

    T nHk(int n, int k) {
        if(n < 0 || k < 0) return 0;
        if(n == 0) return 1;
        else return nCk(n + k - 1, k);
    }

    T Catalan(int n){
        return nCk(2*n, n) - nCk(2*n, n-1);
    }

  private:
    vector<T> _fact, _finv, _inv;

    void update(int sz) {
        if(_fact.size() < sz + 1){
            int pre_sz = max(1, (int)_fact.size());
            _fact.resize(sz + 1, T(1));
            _finv.resize(sz + 1, T(1));
            _inv.resize(sz + 1, T(1));
            for(int i = pre_sz; i <= (int)sz; i++) {
                _fact[i] = _fact[i - 1] * T(i);
            }
            _finv[sz] = T(1) / _fact[sz];
            for(int i = (int)sz - 1; i >= pre_sz; i--) {
                _finv[i] = _finv[i + 1] * T(i + 1);
            }
            for(int i = pre_sz; i <= (int)sz; i++) {
                _inv[i] = _finv[i] * _fact[i - 1];
            }
        }
    }

};

Back to top page