組み合わせ
(atcoder/combination.hpp)

• View this file on GitHub
• Last update: 2021-10-21 18:06:39+09:00
• Include: #include "atcoder/combination.hpp"
• Link: https://ei1333.github.io/luzhiled/snippets/math/combination.html

概要

• fact(k) : $k!$
• rfact(k) : $1/k!$
• inv(k) : $1/k$
• P(n, r) : ${}_nP_r$
• C(n, r) : ${}_nC_r$
• H(n, r) : ${}_nH_r$

制約

• 型テンプレート T には素数を法とする modint を渡す.
• Combination(sz) で初期化した sz より大きい値を使用してはならない.
• modint の法 $P$ 以上の sz で初期化してはいけない.

計算量

• 初期化 Combination(sz) : $O(\mathrm{sz})$
• クエリ : $O(1)$

Verified with

• test/combination.test.cpp

Code

#ifndef ATCODER_COMBINATION_HPP
#define ATCODER_COMBINATION_HPP 1

#include <vector>

namespace atcoder {

// Reference: https://ei1333.github.io/luzhiled/snippets/math/combination.html

template<typename T>
struct Combination {
    std::vector<T> _fact, _rfact, _inv;

    explicit Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {
        _fact[0] = _rfact[sz] = _inv[0] = 1;
        for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;
        _rfact[sz] /= _fact[sz];
        for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);
        for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];
    }

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

    inline T rfact(int k) const { return _rfact[k]; }

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

    T P(int n, int r) const {
        if(r < 0 || n < r) return 0;
        return fact(n) * rfact(n - r);
    }

    T C(int p, int q) const {
        if(q < 0 || p < q) return 0;
        return fact(p) * rfact(q) * rfact(p - q);
    }

    T H(int n, int r) const {
        if(n < 0 || r < 0) return (0);
        return r == 0 ? 1 : C(n + r - 1, r);
    }
};

}  // namespace atcoder

#endif  // ATCODER_COMBINATION_HPP

#line 1 "atcoder/combination.hpp"



#include <vector>

namespace atcoder {

// Reference: https://ei1333.github.io/luzhiled/snippets/math/combination.html

template<typename T>
struct Combination {
    std::vector<T> _fact, _rfact, _inv;

    explicit Combination(int sz) : _fact(sz + 1), _rfact(sz + 1), _inv(sz + 1) {
        _fact[0] = _rfact[sz] = _inv[0] = 1;
        for(int i = 1; i <= sz; i++) _fact[i] = _fact[i - 1] * i;
        _rfact[sz] /= _fact[sz];
        for(int i = sz - 1; i >= 0; i--) _rfact[i] = _rfact[i + 1] * (i + 1);
        for(int i = 1; i <= sz; i++) _inv[i] = _rfact[i] * _fact[i - 1];
    }

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

    inline T rfact(int k) const { return _rfact[k]; }

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

    T P(int n, int r) const {
        if(r < 0 || n < r) return 0;
        return fact(n) * rfact(n - r);
    }

    T C(int p, int q) const {
        if(q < 0 || p < q) return 0;
        return fact(p) * rfact(q) * rfact(p - q);
    }

    T H(int n, int r) const {
        if(n < 0 || r < 0) return (0);
        return r == 0 ? 1 : C(n + r - 1, r);
    }
};

}  // namespace atcoder

Back to top page