FPS の合成逆元の内部処理（高速版）

components/fps_reversion.hpp · GitHub で見る

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

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

compositional_inverse が使う内部部品です。Linux x86_64 / GCC でのみ定義され、呼び出し側が AVX2 対応を実行時に確認します。法は \(p=998244353\) です。

操作	内容・返り値	計算量
native_reversion(in,input,out,n)	合成逆元の先頭 n 係数を空の out へ追加	\(O(n\log^2 n)\)

関数は fps_detail::composition_poly 内にあります。通常は 合成逆元 の compositional_inverse(f,n) を使います。

fps_detail::composition_poly::native_reversion(in,input,out,n) は、内部 Montgomery 係数の input 個の入力から、合成逆元の最初の n 項を空の vector<Mint> である out へ追加します。in と out は重ねず、入力は変更しません。公開側では \(64\le n\le2^{21}\)、入力長 2 以上、\(f_0=0\)、\(f_1\ne0\) の条件で呼びます。入力長を超える係数は 0 として扱います。

射影、添字による除算、反転、冪を同じ Arena 内で連結します。射影の結果から Lagrange 反転公式により合成逆元を求めます。冪の定数項へ Montgomery の倍率を含め、結果を直接 Mint の内部表現として格納します。利用者の配列に整列や padding を要求せず、作業領域の確保失敗時には通常の整列配列へ戻ります。それも失敗した場合は例外となります。

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

依存ライブラリ

• FPS のブロック変換
• FPS の合成・射影の共通変換
• FPS の指数・冪の内部変換
• FPS の結果配列への一括変換
• FPS の射影の専用変換
• FPS の作業領域
• modint998244353 の共通剰余演算
• modint998244353

検証コード

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

コード

#ifndef CP_COMPONENTS_FPS_REVERSION_HPP
#define CP_COMPONENTS_FPS_REVERSION_HPP

#include "fps_projection_blocked.hpp"
#include "fps_exp_blocked.hpp"

#if defined(__linux__) && defined(__x86_64__) && defined(__GNUC__) && !defined(__clang__)
#pragma GCC push_options
_Pragma("GCC target(\"avx2\")")
#pragma GCC optimize("O3")

namespace fps_detail::composition_poly {
inline void native_reversion(const mint *in, std::size_t input, std::vector<mint> &out, std::size_t n) {
	input = std::min(input, n);
	const int lg = std::max(projection_log(n), blocked_poly::power_log(n - 1));
	const std::size_t rest = std::max(projection_scratch(n), Arena::footprint(n - 1) + blocked_poly::power_scratch(n - 1));
	Arena arena(Transform::words(lg) + Arena::footprint(input) + 2 * Arena::footprint(n) + Arena::footprint(rest));
	const Transform t(arena, lg);
	auto f = arena.take(input), g = arena.take(n), a = arena.take(n), scratch = arena.take(rest);
	for (std::size_t i = 0; i < input; ++i) f[i] = coefficient_value(in[i]);
	power_projection(t, f, a, scratch.first(projection_scratch(n)));
	auto h = scratch.first(n - 1);
	blocked_poly::divide_by_index(a.subspan(1), 1, h);
	std::reverse(h.begin(), h.end());
	const auto e = kModulus - blocked_ntt::detail::power(std::uint32_t(n - 1), kModulus - 2);
	const auto c = in[1].inv();
	blocked_poly::power(t, h, e, std::min(c.v, c.v - mint::mod()), g.subspan(1),
						scratch.subspan(Arena::footprint(n - 1), blocked_poly::power_scratch(n - 1)));
	prepare_fps_output(out, n);
	out.emplace_back(0);
	append_fps_words<true>(out, g.data() + 1, g.size() - 1);
}
}
#pragma GCC pop_options
#endif
#endif

Back to top page