形式的冪級数の合成逆元（高速版）

fps/compositional_inverse.hpp · GitHub で見る

全体サイト（256 KiB向け） · 高速実装

軽量実装（64 KiB）はこちら

#include "lib/fps/compositional_inverse.hpp"

fps f{0, 1, 1};
auto inverse = compositional_inverse(f, 5); // {0,1,-1,2,-5}

f は変更しません。法は 998244353、deg は返す係数の個数です。

返る配列は \(g(x)\) の定数項から順に並ぶ係数です。例は \(f(x)=x+x^2\) に対する \(g(x)=x-x^2+2x^3-5x^4\) を 5 係数で返します。コメントの負数は mod 998244353 上の値を表します。入力条件を満たす f を渡すと、指定された長さの逆元が得られます。

操作	内容・返り値	計算量
compositional_inverse(f,deg = -1)	\(f(g(x))=x\bmod x^{\mathrm{deg}}\) となる \(g\)。\(f_0=0\)、長さ 2 以上を求める場合は \(f_1\ne0\)。省略時は f.size()	\(O(n\log^2 n)\)

入出力の最大係数数を \(n\) として、時間 \(O(n\log^2 n)\)、追加空間 \(O(n)\) です。

依存ライブラリ

• FPS のブロック変換
• FPS の合成・射影の共通変換
• FPS の合成・射影の汎用実装
• FPS の融合畳み込み
• FPS の定数係数畳み込み
• FPS の非対称畳み込み
• FPS と多項式除算の内部変換
• FPS の指数・冪の内部変換
• FPS の一点評価
• FPS 逆数のブロック変換
• FPS の内部演算
• FPS の結果配列への一括変換
• FPS の射影の専用変換
• FPS の合成逆元の内部処理（高速版）
• 疎 FPS の共通演算
• 疎 FPS の次数圧縮・前処理
• 疎 FPS の項収集・演算種別
• FPS 平方根のブロック変換
• FPS の作業領域
• modint998244353 の共通剰余演算
• modint998244353 の共有畳み込み
• NTT（998244353）（高速版）
• 多項式の積・打ち切り積の共通処理
• 形式的冪級数（高速版）
• modint998244353

検証コード

• test/fps_compositional_inverse.test.cpp
• test/fps_compositional_inverse_large.test.cpp

コード

#ifndef CP_FPS_COMPOSITIONAL_INVERSE_HPP
#define CP_FPS_COMPOSITIONAL_INVERSE_HPP

#include "fps.hpp"
#include "../components/fps_reversion.hpp"
#include "../components/fps_composition_generic.hpp"

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC push_options
#pragma GCC optimize("O3")
#endif

template<class T>
FormalPowerSeries<T> compositional_inverse(const FormalPowerSeries<T> &f, int deg = -1) {
	using F = FormalPowerSeries<T>;
	using O = fps_detail::Operations<T>;
	if (deg < 0) deg = static_cast<int>(f.size());
	assert(deg >= 0 && (f.empty() || f[0] == T(0)));
	if (deg == 0) return {};
	if (deg == 1) return F(1);
	assert(f.size() >= 2 && f[1] != T(0));
	if constexpr (!std::is_same_v<T, mint>)
		return O::export_work(compositional_inverse<mint>(O::import_work(f), deg));
	else {
		T w = f[1].inv();
		int length = std::min<int>(deg, f.size());
		int first = 2;
		while (first < length && f[first] == T(0)) ++first;
		if (first == length) {
			F result(deg);
			result[1] = w;
			return result;
		}
#if defined(__linux__) && defined(__x86_64__) && defined(__GNUC__) && !defined(__clang__)
		if (deg >= 64 && deg <= (1 << 21) && fps_detail::NTT::vectorized()) {
			F result;
			fps_detail::composition_poly::native_reversion(f.data(), f.size(), result, deg);
			return result;
		}
#endif
		return fps_detail::composition_fallback::compositional_inverse(f, deg);
	}
}

#if defined(__GNUC__) && !defined(__clang__) && (defined(__x86_64__) || defined(__i386__))
#pragma GCC pop_options
#endif

#endif

Back to top page