compositional_inverse

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

// (1)
template <internal::static_modint_c mint>
std::vector<mint> compositional_inverse(const std::vector<mint> &f, int deg);

// (2)
template <internal::static_modint_c mint>
std::vector<mint> compositional_inverse(const std::vector<mint> &f);

概要

(1) 合成逆 (compositional inverse) $g \pmod{x^{deg}}$

$f(g(x)) = g(f(x)) = x \pmod{x^{deg}}$ を満たす $g$ を求める。f[0] == 0 かつ f[1] != 0 が前提。 Kinoshita-Suzuki の power projection (pow_enumerate) で $[x^n] f(x)^k$ を列挙し、 Lagrange-Bürmann 反転 $g = (n^{-1} \log(\mathrm{rev}(h)/h_0))^{-1}$ の $\exp$ で復元する （$h_k = n [x^k] (\text{列挙結果}) / k$）。

• テンプレートパラメータ mint: static modint
• パラメータ f: 係数列（f[0] == 0、f[1] != 0 が必要）
• パラメータ deg: 求める項数
• 戻り値: std::vector<mint> $g(x)$（長さ deg、g[0] == 0）
• 計算量: deg を $d$ として $O(d \log^2 d)$

(2) 合成逆 (compositional inverse) g (deg は f.size())

• テンプレートパラメータ mint: static modint
• パラメータ f: 係数列（f[0] == 0、f[1] != 0 が必要）
• 戻り値: std::vector<mint> 長さ f.size() の g(x)
• 計算量: $n=|f|$ として $O(n\log^2 n)$

関連項目

• 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}}$
• div_mod — 多項式の除算 (商と剰余)
• div — 多項式の商 f / g
• mod — 多項式の剰余 f mod g
• multipoint_evaluation — 多点評価
• polynomial_interpolation — 多項式補間 (ラグランジュ補間)
• taylor_shift — Taylor shift (係数の平行移動)
• shift_of_sampling_points — 標本点のシフト (shift of sampling points)
• inv_of_polynomials — 多項式の逆元 (modular inverse of polynomials)

参照

• https://nyaannyaan.github.io/library/fps/compositional-inverse.hpp