Polynomial taylor shift
(Mylib/Math/polynomial_taylor_shift.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

Required by

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

Verified with

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

Code

#pragma once
#include <vector>

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 2 "Mylib/Math/polynomial_taylor_shift.cpp"
#include <vector>

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

Back to top page