多項式補間（高速版）

fps/interpolate.hpp · GitHub で見る

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

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

#include "lib/fps/interpolate.hpp"

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

法は 998244353 です。xs と ys の長さは等しく、xs の値は法上で相異なる必要があります。入力は変更しません。

xs[i] と ys[i] を一組の点として渡します。例では (0,1),(1,6),(2,17) を通る \(1+2x+3x^2\) が求まります。返り値の f[i] は \(x^i\) の係数で、長さは点数と同じです。点の順番は任意ですが、同じ x 座標を複数渡すことはできません。

操作	内容・返り値	計算量
interpolate(xs,ys)	\(f(x_i)=y_i\) を満たす次数 \(n\) 未満の多項式を FormalPowerSeries<T> で返す。空の入力は空配列	\(O(n\log^2 n)\)

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

依存ライブラリ

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

検証コード

• test/fps_interpolate.test.cpp

コード

#ifndef CP_FPS_INTERPOLATE_HPP
#define CP_FPS_INTERPOLATE_HPP

#include "fps.hpp"
#include "../components/polynomial_product_tree.hpp"
#include "../components/fps_interpolation.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> interpolate(const std::vector<T> &xs, const std::vector<T> &ys) {
	using O = fps_detail::Operations<T>;
	if constexpr (!std::is_same_v<T, mint>) return O::export_work(interpolate<mint>(O::import_work(xs), O::import_work(ys)));
	assert(xs.size() == ys.size());
	const int n = static_cast<int>(xs.size());
	if (n == 0) return {};
#if defined(__linux__) && defined(__x86_64__) && defined(__GNUC__) && !defined(__clang__)
	if constexpr (std::is_same_v<T, mint>) {
		if (n >= 33 && n <= (1 << 23) && fps_detail::NTT::vectorized())
			return FormalPowerSeries<T>(fps_detail::evaluation_poly::native_interpolate(xs, ys));
	}
#endif

	return polynomial_detail::ProductTree<FormalPowerSeries<T>>(xs).interpolate(ys);
}

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

#endif

Back to top page