Catalan number
(Mylib/Combinatorics/catalan_number.cpp)

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

Operations

• catalan_number<ft>(int n) -> T
  • $c_0 = 1, c_{n+1} = \sum_{i=0}^n c_i * c_{n-i}$ を満たす数列の第n項を返す。

Requirements

Notes

Problems

• KUPC2019 D - Maximin Game
• yukicoder No.660 家を通り過ぎないランダムウォーク問題

References

• https://en.wikipedia.org/wiki/Catalan_number
• https://mathtrain.jp/catalan

Depends on

• Factorial table (Mylib/Combinatorics/factorial_table.cpp)

Verified with

• test/yukicoder/660/main.test.cpp

Code

#pragma once
#include <cstdint>
#include "Mylib/Combinatorics/factorial_table.cpp"

namespace haar_lib {
  template <const auto &ft>
  auto catalan_number(int64_t n) {
    return ft.C(2 * n, n) - ft.C(2 * n, n - 1);
  }
}  // namespace haar_lib

#line 2 "Mylib/Combinatorics/catalan_number.cpp"
#include <cstdint>
#line 2 "Mylib/Combinatorics/factorial_table.cpp"
#include <cassert>
#line 4 "Mylib/Combinatorics/factorial_table.cpp"
#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 4 "Mylib/Combinatorics/catalan_number.cpp"

namespace haar_lib {
  template <const auto &ft>
  auto catalan_number(int64_t n) {
    return ft.C(2 * n, n) - ft.C(2 * n, n - 1);
  }
}  // namespace haar_lib

Back to top page