Stirling Second(第二種スターリング数) (math/fps/stirling-second.hpp)

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

Verified with

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

Code

/**
 * @brief Stirling Second(第二種スターリング数)
 */
template <template <typename> class FPS, typename Mint>
FPS<Mint> stirling_second(int N) {
  FPS<Mint> A(N + 1), B(N + 1);
  Mint tmp = 1;
  for (int i = 0; i <= N; i++) {
    Mint rev = Mint(1) / tmp;
    A[i] = Mint(i).pow(N) * rev;
    B[i] = Mint(1) * rev;
    if (i & 1) B[i] *= -1;
    tmp *= i + 1;
  }
  return (A * B).pre(N + 1);
}

#line 1 "math/fps/stirling-second.hpp"
/**
 * @brief Stirling Second(第二種スターリング数)
 */
template <template <typename> class FPS, typename Mint>
FPS<Mint> stirling_second(int N) {
  FPS<Mint> A(N + 1), B(N + 1);
  Mint tmp = 1;
  for (int i = 0; i <= N; i++) {
    Mint rev = Mint(1) / tmp;
    A[i] = Mint(i).pow(N) * rev;
    B[i] = Mint(1) * rev;
    if (i & 1) B[i] *= -1;
    tmp *= i + 1;
  }
  return (A * B).pre(N + 1);
}

Back to top page