Stirling First(第一種スターリング数) (math/fps/stirling-first.hpp)

• View this file on GitHub
• Last update: 2024-05-01 23:44:47+09:00
• Include: #include "math/fps/stirling-first.hpp"

Verified with

• test/verify/yosupo-stirling-number-of-the-first-kind.test.cpp

Code

/**
 * @brief Stirling First(第一種スターリング数)
 */
template <template <typename> class FPS, typename Mint>
FPS<Mint> stirling_first(int N) {
  if (N <= 0) return {Mint(1)};
  auto f = stirling_first<FPS, Mint>(N >> 1);
  f *= f.taylor_shift(-(N >> 1));
  if (N & 1) f = (f << 1) - f * (N - 1);
  return f;
}

#line 1 "math/fps/stirling-first.hpp"
/**
 * @brief Stirling First(第一種スターリング数)
 */
template <template <typename> class FPS, typename Mint>
FPS<Mint> stirling_first(int N) {
  if (N <= 0) return {Mint(1)};
  auto f = stirling_first<FPS, Mint>(N >> 1);
  f *= f.taylor_shift(-(N >> 1));
  if (N & 1) f = (f << 1) - f * (N - 1);
  return f;
}

Back to top page