inv_of_polynomials

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

template <internal::static_modint_c mint>
std::optional<std::vector<mint>> inv_of_polynomials(const std::vector<mint> &f, const std::vector<mint> &g);

概要

多項式の逆元 (modular inverse of polynomials)

$f(x) h(x) \equiv 1 \pmod{g(x)}$ かつ $\deg h < \deg g$ を満たす $h$ を Half-GCD による拡張 Euclid 互除法で求める。 逆元が存在する（$\gcd(f, g)$ が定数）ときのみ値を返し、存在しなければ std::nullopt を返す。 返り値は末尾 $0$ を除いた正規形（逆元が $0$ 多項式のときは空列）。

テンプレートパラメータ

パラメータ

戻り値

std::optional<std::vector<mint>> 逆元 $h$（$\deg h < \deg g$）。逆元が無ければ std::nullopt

計算量

• $n = \max(\deg f, \deg 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}}$
• 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 (係数の平行移動)
• shift_of_sampling_points — 標本点のシフト (shift of sampling points)