seq/interpolate_poly_exp.hpp

• View this file on GitHub
• Last update: 2022-04-16 04:26:49+09:00
• Include: #include "seq/interpolate_poly_exp.hpp"

Required by

• seq/interpolate_poly_exp_sum.hpp

Verified with

• test/library_checker/math/sum_of_exp_times_poly.test.cpp

Code

template <typename mint>
mint interpolate_poly_exp(vc<mint> a, mint r, ll n) {
  // a[i] = r^i * (polynomial of i) となっている場合の補間

  if (r == 0) return (n == 0 ? a[0] : 0);
  mint inv_r = mint(1) / r;
  mint p = 1;
  for (auto&& x: a) {
    x *= p;
    p *= inv_r;
  }
  return lagrange_interpolate_iota(a, mint(n)) * r.pow(n);
}

#line 1 "seq/interpolate_poly_exp.hpp"
template <typename mint>
mint interpolate_poly_exp(vc<mint> a, mint r, ll n) {
  // a[i] = r^i * (polynomial of i) となっている場合の補間

  if (r == 0) return (n == 0 ? a[0] : 0);
  mint inv_r = mint(1) / r;
  mint p = 1;
  for (auto&& x: a) {
    x *= p;
    p *= inv_r;
  }
  return lagrange_interpolate_iota(a, mint(n)) * r.pow(n);
}

Back to top page