多項式の評価点シフト (src/Math/sample_points_shift.hpp)

• View this file on GitHub
• View document part on GitHub
• Last update: 2024-10-14 13:39:24+09:00
• Include: #include "src/Math/sample_points_shift.hpp"

名前	概要	計算量
sample_points_shift(y,c)	$n-1$ 次多項式 $f(x)$ について $n$ 個の評価点 $y=f(0), f(1), \dots, f(n-1)$ と $c$ を与えて $f(c)$ を返す．	$O(n)$

Verify

• AtCoder Regular Contest 033 D - 見たことのない多項式

Depends on

• modintを扱うテンプレート (src/Internal/modint_traits.hpp)
• 二項係数 他 (階乗前計算) ($\mathbb{F}_p$) (src/Math/FactorialPrecalculation.hpp)

Verified with

• test/atcoder/abc198_f.interpolate.test.cpp
• test/atcoder/abc208_f.test.cpp
• test/atcoder/s8pc_3_g.test.cpp
• test/misc/cf_contest622_f.test.cpp
• test/sample_test/arc033_4.test.cpp
• test/yosupo/sum_of_exponential_times_polynomial.test.cpp
• test/yukicoder/42.test.cpp
• test/yukicoder/665.test.cpp

Code

#pragma once
#include "src/Math/FactorialPrecalculation.hpp"
// given: f(0),f(1),...,f(n-1), c   output: f(c)    O(n)
template <class mod_t> mod_t sample_points_shift(std::vector<mod_t> y, mod_t c) {
 using F= FactorialPrecalculation<mod_t>;
 int n= y.size();
 if ((int)c.val() < n) return y[c.val()];
 for (int i= n; i--;) y[i]*= F::finv(i) * F::finv(n - i - 1);
 for (int i= 1; i < n; i+= 2) y[n - i - 1]= -y[n - i - 1];
 mod_t t= 1, ret= 0;
 for (int i= n; i--;) y[i]*= t, t*= c - i;
 t= 1;
 for (int i= 0; i < n; ++i) ret+= y[i] * t, t*= c - i;
 return ret;
}

#line 2 "src/Math/FactorialPrecalculation.hpp"
#include <cassert>
#include <vector>
#line 2 "src/Internal/modint_traits.hpp"
#include <type_traits>
namespace math_internal {
struct m_b {};
struct s_b: m_b {};
}
template <class mod_t> constexpr bool is_modint_v= std::is_base_of_v<math_internal::m_b, mod_t>;
template <class mod_t> constexpr bool is_staticmodint_v= std::is_base_of_v<math_internal::s_b, mod_t>;
#line 5 "src/Math/FactorialPrecalculation.hpp"
template <class mod_t> class FactorialPrecalculation {
 static_assert(is_modint_v<mod_t>);
 static inline std::vector<mod_t> iv, fct, fiv;
public:
 static void reset() { iv.clear(), fct.clear(), fiv.clear(); }
 static inline mod_t inv(int n) {
  assert(0 < n);
  if (int k= iv.size(); k <= n) {
   if (iv.resize(n + 1); !k) iv[1]= 1, k= 2;
   for (unsigned long long mod= mod_t::mod(), q; k <= n; ++k) q= (mod + k - 1) / k, iv[k]= iv[k * q - mod] * q;
  }
  return iv[n];
 }
 static inline mod_t fact(int n) {
  assert(0 <= n);
  if (int k= fct.size(); k <= n) {
   if (fct.resize(n + 1); !k) fct[0]= 1, k= 1;
   for (; k <= n; ++k) fct[k]= fct[k - 1] * k;
  }
  return fct[n];
 }
 static inline mod_t finv(int n) {
  assert(0 <= n);
  if (int k= fiv.size(); k <= n) {
   if (fiv.resize(n + 1); !k) fiv[0]= 1, k= 1;
   for (; k <= n; ++k) fiv[k]= fiv[k - 1] * inv(k);
  }
  return fiv[n];
 }
 static inline mod_t nPr(int n, int r) { return r < 0 || n < r ? mod_t(0) : fact(n) * finv(n - r); }
 // [x^r] (1 + x)^n
 static inline mod_t nCr(int n, int r) { return r < 0 || n < r ? mod_t(0) : fact(n) * finv(n - r) * finv(r); }
 // [x^r] (1 - x)^{-n}
 static inline mod_t nHr(int n, int r) { return !r ? mod_t(1) : nCr(n + r - 1, r); }
};
#line 3 "src/Math/sample_points_shift.hpp"
// given: f(0),f(1),...,f(n-1), c   output: f(c)    O(n)
template <class mod_t> mod_t sample_points_shift(std::vector<mod_t> y, mod_t c) {
 using F= FactorialPrecalculation<mod_t>;
 int n= y.size();
 if ((int)c.val() < n) return y[c.val()];
 for (int i= n; i--;) y[i]*= F::finv(i) * F::finv(n - i - 1);
 for (int i= 1; i < n; i+= 2) y[n - i - 1]= -y[n - i - 1];
 mod_t t= 1, ret= 0;
 for (int i= n; i--;) y[i]*= t, t*= c - i;
 t= 1;
 for (int i= 0; i < n; ++i) ret+= y[i] * t, t*= c - i;
 return ret;
}

Back to top page