Bernoulli(ベルヌーイ数) (math/fps/bernoulli.hpp)

View this file on GitHub
Last update: 2024-04-27 01:27:28+09:00
Include: #include "math/fps/bernoulli.hpp"

Verified with

test/verify/yosupo-bernoulli-number.test.cpp

Code

/**
 * @brief Bernoulli(ベルヌーイ数)
 */
template <template <typename> class FPS, typename Mint>
FPS<Mint> bernoulli(int N) {
  FPS<Mint> poly(N + 1);
  poly[0] = Mint(1);
  for (int i = 1; i <= N; i++) {
    poly[i] = poly[i - 1] / Mint(i + 1);
  }
  poly = poly.inv();
  Mint tmp(1);
  for (int i = 1; i <= N; i++) {
    tmp *= Mint(i);
    poly[i] *= tmp;
  }
  return poly;
}

#line 1 "math/fps/bernoulli.hpp"
/**
 * @brief Bernoulli(ベルヌーイ数)
 */
template <template <typename> class FPS, typename Mint>
FPS<Mint> bernoulli(int N) {
  FPS<Mint> poly(N + 1);
  poly[0] = Mint(1);
  for (int i = 1; i <= N; i++) {
    poly[i] = poly[i - 1] / Mint(i + 1);
  }
  poly = poly.inv();
  Mint tmp(1);
  for (int i = 1; i <= N; i++) {
    tmp *= Mint(i);
    poly[i] *= tmp;
  }
  return poly;
}