Stirling numbers of the first kind (FFT)
(Mylib/Combinatorics/stirling_number_first_fft.cpp)

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

Operations

Requirements

Notes

Problems

References

Depends on

• Polynomial taylor shift (Mylib/Math/polynomial_taylor_shift.cpp)

Verified with

• test/yosupo-judge/stirling_number_of_the_first_kind/main.test.cpp

Code

#pragma once
#include <algorithm>
#include <vector>
#include "Mylib/Math/polynomial_taylor_shift.cpp"

namespace haar_lib {
  template <typename T, const auto &convolve>
  std::vector<T> stirling_number_of_first_kind_fft(int N) {
    if (N == 0) return {1};

    std::vector<int> p;
    {
      int a = N;

      while (a > 0) {
        if (a & 1) p.push_back(1);
        p.push_back(2);
        a >>= 1;
      }
    }

    std::vector<T> ret = {1};

    std::reverse(p.begin(), p.end());
    int t = 0;
    for (int x : p) {
      if (x == 1) {
        std::vector<T> a = {-t, 1};
        ret              = convolve(ret, a);

        t += 1;
      } else {
        auto s = polynomial_taylor_shift<T, convolve>(ret, -t);
        ret    = convolve(ret, s);
        ret.resize(t * 2 + 1);

        t *= 2;
      }
    }

    ret.resize(N + 1);

    return ret;
  }
}  // namespace haar_lib

#line 2 "Mylib/Combinatorics/stirling_number_first_fft.cpp"
#include <algorithm>
#include <vector>
#line 3 "Mylib/Math/polynomial_taylor_shift.cpp"

namespace haar_lib {
  template <typename T, const auto &convolve>
  auto polynomial_taylor_shift(std::vector<T> a, T c) {
    const int N = a.size();
    T f         = 1;

    std::vector<T> A(2 * N - 1);
    for (int i = 0; i < N; ++i) {
      if (i) f *= i;
      A[i + N - 1] = a[i] * f;
    }

    T d = 1;

    std::vector<T> g(N);
    g[N - 1] = f.inv();
    for (int i = N - 2; i >= 0; --i) g[i] = g[i + 1] * (i + 1);

    std::vector<T> B(2 * N - 1);
    for (int i = 0; i < N; ++i) {
      B[N - i - 1] = d * g[i];
      d *= c;
    }

    auto C = convolve(A, B);

    std::vector<T> ret(N);
    for (int i = 0; i < N; ++i) ret[i] = C[(N - 1) * 2 + i] * g[i];

    return ret;
  }
}  // namespace haar_lib
#line 5 "Mylib/Combinatorics/stirling_number_first_fft.cpp"

namespace haar_lib {
  template <typename T, const auto &convolve>
  std::vector<T> stirling_number_of_first_kind_fft(int N) {
    if (N == 0) return {1};

    std::vector<int> p;
    {
      int a = N;

      while (a > 0) {
        if (a & 1) p.push_back(1);
        p.push_back(2);
        a >>= 1;
      }
    }

    std::vector<T> ret = {1};

    std::reverse(p.begin(), p.end());
    int t = 0;
    for (int x : p) {
      if (x == 1) {
        std::vector<T> a = {-t, 1};
        ret              = convolve(ret, a);

        t += 1;
      } else {
        auto s = polynomial_taylor_shift<T, convolve>(ret, -t);
        ret    = convolve(ret, s);
        ret.resize(t * 2 + 1);

        t *= 2;
      }
    }

    ret.resize(N + 1);

    return ret;
  }
}  // namespace haar_lib

Back to top page