composition
関数 · 形式的冪級数 (FPS)
// (1)
template <internal::static_modint_c mint>
std::vector<mint> composition(const std::vector<mint> &outer, const std::vector<mint> &inner, int deg);
// (2)
template <internal::static_modint_c mint>
std::vector<mint> composition(const std::vector<mint> &f, const std::vector<mint> &g);
概要
(1) 合成 (composition) $f(g(x)) \pmod{x^{deg}}$
$h(x) = f(g(x)) = \sum_i f_i g(x)^i \pmod{x^{deg}}$ を Kinoshita-Suzuki の分割統治で求める。 Nyaan の composition は $g(f(x))$ を返すため f と g を入れ替えて呼び出す。 f は多項式として扱うため g[0] != 0 でも正しく計算できる。
- テンプレートパラメータ
mint: static modint - パラメータ
f: 外側の係数列 - パラメータ
g: 内側の係数列 - パラメータ
deg: 求める項数 - 戻り値:
std::vector<mint>$f(g(x))$（長さdeg） - 計算量:
degを $d$ として $O(d \log^2 d)$
(2) 合成 (composition) f(g(x)) (deg は max(f.size(), g.size()))
- テンプレートパラメータ
mint: static modint - パラメータ
f: 外側の係数列 - パラメータ
g: 内側の係数列 - 戻り値:
std::vector<mint>f(g(x)) - 計算量: $n=\max(|f|,|g|)$ として $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}}$compositional_inverse— 合成逆 (compositional inverse) $g \pmod{x^{deg}}$div_mod— 多項式の除算 (商と剰余)div— 多項式の商 f / gmod— 多項式の剰余 f mod gmultipoint_evaluation— 多点評価polynomial_interpolation— 多項式補間 (ラグランジュ補間)taylor_shift— Taylor shift (係数の平行移動)shift_of_sampling_points— 標本点のシフト (shift of sampling points)inv_of_polynomials— 多項式の逆元 (modular inverse of polynomials)