多点評価・補間の内部木（高速版）

components/fps_product_tree.hpp · GitHub で見る

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

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

fps_detail::ProductTree<T> は 多点評価・補間が共有する内部部品です。通常は各関数の公開ヘッダーを include してください。

共通積木に FormalPowerSeries<T> を渡した実装を継承します。ProductTree<T>(xs) で構築し、tree.evaluate(f)・tree.interpolate(ys) を使えます。点列と同じ順序で評価し、補間では互いに異なる点を使います。内部の積・剰余・微分は高速 FPS に委譲します。

従来の static API も互換用に残しています。

内部 API	内容・返り値
build(xs,size,block,reciprocal,frequency = nullptr)	block 点ずつの一次式をまとめた木を返す。size を必要な 2 冪まで増やす。reciprocal が真なら各葉の積は \(\displaystyle\prod_j(1-x_jx)\)、偽なら \(\displaystyle\prod_j(x-x_j)\)
evaluate(points,tree,frequency,size,block,root,consume = false)	従来の中間表現 root から多項式を復元し、共通積木で評価する

互換 API の frequency は変換キャッシュを保持せず、build では空の各要素で初期化します。static evaluate の frequency・consume は結果に影響しません。専用 SIMD 木の経路は評価・補間の専用実装が扱います。

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

依存ライブラリ

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

検証コード

• test/multipoint_eval.test.cpp

コード

#ifndef CP_COMPONENTS_FPS_PRODUCT_TREE_HPP
#define CP_COMPONENTS_FPS_PRODUCT_TREE_HPP

#include "../fps/fps.hpp"
#include "polynomial_product_tree.hpp"

namespace fps_detail {
template<class T>
struct ProductTree : polynomial_detail::ProductTree<FormalPowerSeries<T>> {
	using F = FormalPowerSeries<T>;
	using Base = polynomial_detail::ProductTree<F>;
	using Base::Base, Base::evaluate;

	static std::vector<F> build(const std::vector<T>& xs, int& size, int block, bool reciprocal,
			std::vector<std::vector<T>>* frequency = nullptr) {
		const int groups = (static_cast<int>(xs.size()) + block - 1) / block;
		while (size < groups) size <<= 1;
		std::vector<F> tree(2 * size, F{T(1)});
		if (frequency) frequency->assign(2 * size, {});
		for (int i = 0; i < groups; ++i) {
			F& p = tree[size + i];
			p.reserve(block + 1);
			for (int j = i * block; j < std::min<int>((i + 1) * block, xs.size()); ++j) {
				p.push_back(T(0));
				if (reciprocal) {
					for (int k = p.size() - 1; k >= 1; --k) p[k] -= xs[j] * p[k - 1];
				} else {
					for (int k = p.size() - 1; k >= 1; --k) p[k] = p[k - 1] - xs[j] * p[k];
					p[0] *= -xs[j];
				}
			}
		}
		for (int i = size - 1; i; --i)
			tree[i] = tree[2 * i + 1].size() == 1 ? tree[2 * i] : Base::multiply(tree[2 * i], tree[2 * i + 1]);
		return tree;
	}

	static std::vector<T> evaluate(const std::vector<T>& points, const std::vector<F>& tree,
			std::vector<std::vector<T>>&, int size, int block, F root, bool = false) {
		F f = Base::multiply_low(root, tree[1], size * block);
		std::reverse(f.begin(), f.end());
		return Base(points).evaluate(f);
	}

};
}

#endif

Back to top page