多点評価・補間の内部木（軽量版）

components/fps_light_product_tree.hpp · GitHub で見る

64 KiBサイト · 軽量実装

高速実装（256 KiB向け）はこちら

#include "lib/components/fps_light_product_tree.hpp"

std::vector<mint> xs{0, 1, 2};
fps_light_detail::ProductTree<mint> tree(xs);
auto values = tree.evaluate(light_fps{1, 2, 3}); // {1,6,17}

軽量 FPS の多点評価・補間 が共有する内部部品です。fps_light_detail::ProductTree<T> は共通積木の ProductTree<LightFormalPowerSeries<T>> の別名です。各葉に一次式を置き、上の節点ほど積を保持します。評価は多項式の剰余を子へ渡して行います。通常は公開関数 light_fps_algorithms::multipoint_eval・interpolate を使ってください。

要素	内容
ProductTree<T>(xs)	評価点から積木を構築。点の重複・空の点列を許す
tree.evaluate(f)	xs の順の評価値を std::vector<T> で返す
tree.interpolate(ys)	対応する値から点数と同じ係数数の LightFormalPowerSeries<T> を返す。点は互いに異なる必要がある
tree.count / tree.size	点数／点数以上の最小の 2 冪（空なら 1）
tree.product	1 始まりの節点配列。添字 0 は未使用

product[1] は \(\displaystyle \prod_{i=0}^{m-1}(x-x_i)\) です。空の点列では定数多項式 1 です。product[size+i] は有効な点では \(x-x_i\)、末尾の埋め草では定数 1 です。構築後は product・size・count を変更しないでください。

法と係数型は 軽量 FPS と同じ条件です。点数は \(2^{23}\) 以下です。最上位の積が畳み込みの上限を超える場合は、共通積木が分割して計算します。評価する多項式の長さと、剰余計算などに必要な長さも軽量 FPS の上限に収めてください。

点数を \(m\)、評価する多項式の係数数を \(n\) として、構築・補間は \(O(m\log^2 m)\) 時間、木の保持は \(O(m\log m)\) 空間です。補間は \(O(m)\) 追加空間、評価は \(O((n+m)\log^2(n+m))\) 時間・\(O(n+m)\) 追加空間で、構築済みの積木の空間は別に必要です。

依存ライブラリ

• FPS の互換ヘッダー（軽量版）
• 軽量 FPS の基本演算
• NTT（998244353）（軽量版）
• 軽量 FPS の疎演算
• 疎 FPS の項収集・演算種別
• 多項式の積・打ち切り積の共通処理
• 多項式の共通積木
• modint998244353

コード

#ifndef FPS_LIGHT_PRODUCT_TREE_HPP
#define FPS_LIGHT_PRODUCT_TREE_HPP
#include "fps_light_backend.hpp"
#endif

Back to top page