多点評価（高速版）

fps/multipoint_eval.hpp · GitHub で見る

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

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

#include "lib/fps/multipoint_eval.hpp"

fps f{1, 2, 3};
std::vector<mint> xs{0, 1, 2};
auto values = multipoint_eval(f, xs); // {1,6,17}

法は 998244353 です。評価点の重複を許し、入力は変更しません。

f={1,2,3} は \(1+2x+3x^2\) です。values[i] は f(xs[i]) で、点をソートする必要はありません。values.size() == xs.size() となり、同じ点を複数渡した場合もそれぞれの位置に答えが入ります。mint の値を通常の整数にするには values[i].val() を使います。

操作	内容・返り値	計算量
multipoint_eval(f,xs)	xs の順に多項式の値を返す。返り値は vector<T>。空の点列は空配列	\(O((n+m)\log^2(n+m))\)

係数数を \(n\)、点数を \(m\) として、時間 \(O((n+m)\log^2(n+m))\)、追加空間 \(O((n+m)\log(n+m))\) です。

依存ライブラリ

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

検証コード

• test/multipoint_eval.test.cpp

コード

#ifndef CP_FPS_MULTIPOINT_EVAL_HPP
#define CP_FPS_MULTIPOINT_EVAL_HPP

#include "fps.hpp"
#include "../components/fps_product_tree.hpp"
#include "../components/fps_direct_eval.hpp"
#include "../components/fps_multipoint.hpp"

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

template<class T>
std::vector<T> multipoint_eval(const FormalPowerSeries<T> &f, const std::vector<T> &xs) {
	using W = FormalPowerSeries<mint>;
	using base = std::vector<T>;
	using O = fps_detail::Operations<T>;
	if constexpr (!std::is_same_v<T, mint>) return O::export_work(W(multipoint_eval<mint>(O::import_work(f), O::import_work(xs))));
	if (xs.empty()) return {};
	if (f.size() <= 32 || xs.size() <= 32) {
#if defined(__x86_64__) || defined(__i386__)
		if constexpr (std::is_same_v<T, mint>) {
			if (((xs.size() >= 8 && f.size() >= 8 && (xs.size() >= 32 || f.size() >= 32)) ||
				 (xs.size() >= 4096 && f.size() >= 4)) && fps_detail::NTT::vectorized()) {
				base r(xs.size());
				fps_detail::evaluate_direct(O::words(r), O::words(f), f.size(), O::words(xs), xs.size());
				return r;
			}
		}
#endif
		base r;
		r.reserve(xs.size());
		for (T x : xs) r.push_back(f.eval(x));
		return r;
	}
#if defined(__x86_64__) || defined(__i386__)
	if constexpr (std::is_same_v<T, mint>) {
		if (f.size() * xs.size() <= (std::size_t(1) << 14) && fps_detail::NTT::vectorized()) {
			base result(xs.size());
			fps_detail::evaluate_direct(O::words(result), O::words(f), f.size(), O::words(xs), xs.size());
			return result;
		}
	}
#endif
#if defined(__linux__) && defined(__x86_64__) && defined(__GNUC__) && !defined(__clang__)
	if constexpr (std::is_same_v<T, mint>) {
		if (std::max(f.size(), xs.size()) <= (1 << 23) && fps_detail::NTT::vectorized()) {
			if (xs.size() <= 512 && f.size() > 4 * xs.size()) {
				int size = 1;
				const auto tree = fps_detail::ProductTree<T>::build(xs, size, 8, false);
				return fps_detail::evaluation_poly::native_evaluate(f.divmod(tree[1]).second, xs);
			}
			return fps_detail::evaluation_poly::native_evaluate(f, xs);
		}
	}
#endif

	return fps_detail::ProductTree<T>(xs).evaluate(f);
}

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

#endif

Back to top page