Combination
(math/combination.cpp)

• View this file on GitHub
• Last update: 2023-05-27 03:55:18+09:00

Description

階乗 $n!$，組み合わせ $n \choose r$，順列 $_n \mathrm{P} _r$ を法 $mod$ で計算する．

空間計算量: $O(n)$

Operations

• Combination(int n)
  • $n$ 以下の整数の階乗及びその逆元を前計算する
  • 時間計算量: $O(n)$
• T perm(int n, int r)
  • $_n \mathrm{P} _r$ を計算する．$r < 0$ または $n < r$ のときは0を返す
  • 時間計算量: $O(1)$
• T comb(int n, int r)
  • $n \choose r$ を計算する．$r < 0$ または $n < r$ のときは0を返す
  • 時間計算量: $O(1)$
• T fact(int n)
  • $n!$ を計算する
  • 時間計算量: $O(1)$
• T fact_inv(int n)
  • $n!$ の逆元を計算する
  • 時間計算量: $O(1)$

以下の関数はCombinationクラスに含まれない

• T comb(int n, int r)
  • $n \choose r$ を計算する．
  • 時間計算量: $O(r)$

Required by

• Stirling Number of the Second Kind (math/stirling_second.hpp)

Verified with

• test/yosupo/binomial_coefficient_prime_mod.test.cpp
• test/yosupo/stirling_number_of_the_second_kind.test.cpp

Code

#pragma once
#include <vector>

template <typename mint>
class Combination {
   public:
    Combination() = default;
    Combination(int n) : fact_(n + 1), fact_inv_(n + 1) {
        fact_[0] = 1;
        for (int i = 1; i <= n; ++i) fact_[i] = fact_[i - 1] * i;
        fact_inv_[n]=fact_[n].inv();
        for (int i = n; i > 0; --i) fact_inv_[i - 1] = fact_inv_[i] * i;
    }

    mint perm(int n, int k) const {
        if (k < 0 || n < k) return 0;
        return fact_[n] * fact_inv_[n - k];
    }

    mint comb(int n, int k) const {
        if (k < 0 || n < k) return 0;
        return fact_[n] * fact_inv_[k] * fact_inv_[n - k];
    }

    mint fact(int n) const { return fact_[n]; }
    mint fact_inv(int n) const { return fact_inv_[n]; }

   private:
    std::vector<mint> fact_, fact_inv_;
};

template <typename T>
T comb(long long n, int k) {
    if (k < 0 || n < k) return 0;
    T num = 1, den = 1;
    for (int i = 1; i <= k; ++i) {
        num = num * (n - i + 1);
        den = den * i;
    }
    return num / den;
}

#line 2 "math/combination.cpp"
#include <vector>

template <typename mint>
class Combination {
   public:
    Combination() = default;
    Combination(int n) : fact_(n + 1), fact_inv_(n + 1) {
        fact_[0] = 1;
        for (int i = 1; i <= n; ++i) fact_[i] = fact_[i - 1] * i;
        fact_inv_[n]=fact_[n].inv();
        for (int i = n; i > 0; --i) fact_inv_[i - 1] = fact_inv_[i] * i;
    }

    mint perm(int n, int k) const {
        if (k < 0 || n < k) return 0;
        return fact_[n] * fact_inv_[n - k];
    }

    mint comb(int n, int k) const {
        if (k < 0 || n < k) return 0;
        return fact_[n] * fact_inv_[k] * fact_inv_[n - k];
    }

    mint fact(int n) const { return fact_[n]; }
    mint fact_inv(int n) const { return fact_inv_[n]; }

   private:
    std::vector<mint> fact_, fact_inv_;
};

template <typename T>
T comb(long long n, int k) {
    if (k < 0 || n < k) return 0;
    T num = 1, den = 1;
    for (int i = 1; i <= k; ++i) {
        num = num * (n - i + 1);
        den = den * i;
    }
    return num / den;
}

Back to top page