Bernoulli number
(Mylib/Combinatorics/bernoulli_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

• bernoulli_number<ft>(int n) -> [T]
  • $B_0$ ~ $B_n$を列挙する。
  • Time complexity $O(N^2)$

Requirements

Notes

Problems

References

• https://ja.wikipedia.org/wiki/%E3%83%99%E3%83%AB%E3%83%8C%E3%83%BC%E3%82%A4%E6%95%B0

Depends on

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

Verified with

• test/yukicoder/665/main.test.cpp

Code

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

namespace haar_lib {
  template <
      const auto &ft,
      typename T = typename std::remove_reference_t<decltype(ft)>::value_type>
  std::vector<T> bernoulli_number(int n) {
    std::vector<T> ret(n + 1);

    ret[0] = 1;

    for (int64_t i = 1; i <= n; ++i) {
      for (int k = 0; k <= i - 1; ++k) {
        ret[i] += ft.C(i + 1, k) * ret[k];
      }
      ret[i] /= i + 1;
      ret[i] = -ret[i];
    }

    return ret;
  }
}  // namespace haar_lib

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

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 5 "Mylib/Combinatorics/bernoulli_number.cpp"

namespace haar_lib {
  template <
      const auto &ft,
      typename T = typename std::remove_reference_t<decltype(ft)>::value_type>
  std::vector<T> bernoulli_number(int n) {
    std::vector<T> ret(n + 1);

    ret[0] = 1;

    for (int64_t i = 1; i <= n; ++i) {
      for (int k = 0; k <= i - 1; ++k) {
        ret[i] += ft.C(i + 1, k) * ret[k];
      }
      ret[i] /= i + 1;
      ret[i] = -ret[i];
    }

    return ret;
  }
}  // namespace haar_lib

Back to top page