shift_of_sampling_points

関数 · 形式的冪級数 (FPS)

template <internal::static_modint_c mint>
std::vector<mint> shift_of_sampling_points(const std::vector<mint> &y, mint c, int m);

概要

標本点のシフト (shift of sampling points)

次数 $< n$ の多項式 $f$ の標本値 $y_i = f(i)$（$i = 0, \ldots, n-1$）から $f(c), f(c+1), \ldots, f(c+m-1)$ を求める。 ラグランジュ補間 $f(x) = \left(\prod_k (x-k)\right) \sum_i a_i / (x-i)$ を、係数 $a_i = y_i / \prod_{k \ne i} (i-k)$ と $1/(c+t)$ の畳み込みで一括評価する。 評価点 $c+j$ が標本点 $\{0, \ldots, n-1\}$ と一致する（区間積が $0$ になる）場合は y を直接返す。

テンプレートパラメータ

パラメータ

戻り値

std::vector<mint> $f(c+j)$ の列（$j = 0, \ldots, m-1$、長さ $m$）

計算量

• $O((n + m) \log(n + m))$

関連項目

• plus — 形式的冪級数の加算
• inv — 逆元 $1 / h \pmod{x^{deg}}$
• log — 対数 $\log h \pmod{x^{deg}}$
• exp — 指数 $\exp h \pmod{x^{deg}}$
• pow — 冪乗 $h^m \pmod{x^{deg}}$
• sqrt — 平方根 $\sqrt h \pmod{x^{deg}}$
• composition — 合成 (composition) $f(g(x)) \pmod{x^{deg}}$
• compositional_inverse — 合成逆 (compositional inverse) $g \pmod{x^{deg}}$
• div_mod — 多項式の除算 (商と剰余)
• div — 多項式の商 f / g
• mod — 多項式の剰余 f mod g
• multipoint_evaluation — 多点評価
• polynomial_interpolation — 多項式補間 (ラグランジュ補間)
• taylor_shift — Taylor shift (係数の平行移動)
• inv_of_polynomials — 多項式の逆元 (modular inverse of polynomials)