Factorial table
(Mylib/Combinatorics/factorial_table.cpp)

• View this file on GitHub
• Last update: 2021-04-23 23:44:44+09:00
• Link: View error logs on GitHub Actions

Operations

• factorial_table(int N)
  • $0!$ ~ $N!$とその逆数を計算する。
  • Time complexity $O(N)$
• factorial(int i) : return $i!$
• inv_factorial(int i) : return $\frac{1}{i!}$
• P(int n, int k) : return $_nP_k$
• C(int n, int k) : return $_nC_k$
• H(int n, int k) : return $_nH_k = _{n+k-1}C_k$

Requirements

Notes

Problems

References

Required by

• Bell number (Mylib/Combinatorics/bell_number.cpp)
• Bernoulli number (Mylib/Combinatorics/bernoulli_number.cpp)
• Catalan number (Mylib/Combinatorics/catalan_number.cpp)
• Stirling numbers of the second kind (Mylib/Combinatorics/stirling_number_second.cpp)

Verified with

• test/aoj/DPL_5_G/main.test.cpp
• test/aoj/DPL_5_I/main.test.cpp
• test/yosupo-judge/bernoulli_number/main.test.cpp
• test/yukicoder/117/main.test.cpp
• test/yukicoder/660/main.test.cpp
• test/yukicoder/665/main.test.cpp

Code

#pragma once
#include <cassert>
#include <cstdint>
#include <vector>

namespace haar_lib {
  template <typename T>
  class factorial_table {
  public:
    using value_type = T;

  private:
    int N_;
    std::vector<T> f_table_, if_table_;

  public:
    factorial_table() {}
    factorial_table(int N) : N_(N) {
      f_table_.assign(N + 1, 1);
      if_table_.assign(N + 1, 1);

      for (int i = 1; i <= N; ++i) {
        f_table_[i] = f_table_[i - 1] * i;
      }

      if_table_[N] = f_table_[N].inv();

      for (int i = N; --i >= 0;) {
        if_table_[i] = if_table_[i + 1] * (i + 1);
      }
    }

    T factorial(int64_t i) const {
      assert(0 <= i and i <= N_);
      return f_table_[i];
    }

    T inv_factorial(int64_t i) const {
      assert(0 <= i and i <= N_);
      return if_table_[i];
    }

    T P(int64_t n, int64_t k) const {
      if (n < k or n < 0 or k < 0) return 0;
      return factorial(n) * inv_factorial(n - k);
    }

    T C(int64_t n, int64_t k) const {
      if (n < k or n < 0 or k < 0) return 0;
      return P(n, k) * inv_factorial(k);
    }

    T H(int64_t n, int64_t k) const {
      if (n == 0 and k == 0) return 1;
      return C(n + k - 1, k);
    }
  };
}  // namespace haar_lib

#line 2 "Mylib/Combinatorics/factorial_table.cpp"
#include <cassert>
#include <cstdint>
#include <vector>

namespace haar_lib {
  template <typename T>
  class factorial_table {
  public:
    using value_type = T;

  private:
    int N_;
    std::vector<T> f_table_, if_table_;

  public:
    factorial_table() {}
    factorial_table(int N) : N_(N) {
      f_table_.assign(N + 1, 1);
      if_table_.assign(N + 1, 1);

      for (int i = 1; i <= N; ++i) {
        f_table_[i] = f_table_[i - 1] * i;
      }

      if_table_[N] = f_table_[N].inv();

      for (int i = N; --i >= 0;) {
        if_table_[i] = if_table_[i + 1] * (i + 1);
      }
    }

    T factorial(int64_t i) const {
      assert(0 <= i and i <= N_);
      return f_table_[i];
    }

    T inv_factorial(int64_t i) const {
      assert(0 <= i and i <= N_);
      return if_table_[i];
    }

    T P(int64_t n, int64_t k) const {
      if (n < k or n < 0 or k < 0) return 0;
      return factorial(n) * inv_factorial(n - k);
    }

    T C(int64_t n, int64_t k) const {
      if (n < k or n < 0 or k < 0) return 0;
      return P(n, k) * inv_factorial(k);
    }

    T H(int64_t n, int64_t k) const {
      if (n == 0 and k == 0) return 1;
      return C(n + k - 1, k);
    }
  };
}  // namespace haar_lib

Back to top page