cp-library

競技プログラミング用 C++ ライブラリ

View the Project on GitHub qandori/cp-library

:heavy_check_mark: 軽量 FPS の共通実装

components/fps_light_backend.hpp · GitHub で見る

共通ページ · 軽量実装

FPS の互換ヘッダーの高速実装はこちら

軽量 FPS と追加演算の共通部品です。通常は公開ヘッダーを include してください。

FPS の公開ヘッダーは fps/fps_light.hpp・fps/fps_light_algorithms.hpp、積木は components/fps_light_product_tree.hpp です。NTT だけを使う場合は components/fps_light_ntt.hpp を読み込みます。複数を include しても定義は一度だけで、通常版 FPS の実装は読み込みません。

FPS の型と基本演算は 基本演算の共通部品 に置き、このヘッダーで積木と追加演算を組み合わせます。基本演算だけが必要な内部部品は components/fps_light_core.hpp を include できます。

依存ライブラリ

検証コード

コード

#ifndef CP_FPS_LIGHT_BACKEND_HPP
#define CP_FPS_LIGHT_BACKEND_HPP

#include "fps_light_core.hpp"
#include "polynomial_product_tree.hpp"

namespace fps_light_detail {
template<class T>
using ProductTree = polynomial_detail::ProductTree<LightFormalPowerSeries<T>>;
}

namespace light_fps_algorithms {
template<class T>
LightFormalPowerSeries<T> taylor_shift(LightFormalPowerSeries<T> f, std::type_identity_t<T> c) {
	using F = LightFormalPowerSeries<T>;
	const std::size_t n = f.size();
	if (n <= 1 || c == T(0)) return f;
	assert(n < T::mod());
	F a(n), b(n);
	T factorial = 1;
	a[n - 1] = f[0];
	for (std::size_t i = 1; i < n; ++i) {
		factorial *= T(i);
		a[n - 1 - i] = f[i] * factorial;
	}
	f[n - 1] = factorial.inv();
	for (std::size_t i = n - 1; i; --i) f[i - 1] = f[i] * T(i);
	T power = 1;
	for (std::size_t i = 0; i < n; ++i) {
		b[i] = power * f[i];
		power *= c;
	}
	a = F::multiply(a, b);
	for (std::size_t i = 0; i < n; ++i) f[i] *= a[n - 1 - i];
	return f;
}

template<class T>
T bostan_mori(LightFormalPowerSeries<T> p, LightFormalPowerSeries<T> q, long long k) {
	using F = LightFormalPowerSeries<T>;
	assert(k >= 0 && !q.empty() && q[0] != T(0));
	p.shrink();
	q.shrink();
	while (k && !p.empty() && q.size() > 1) {
		F even((q.size() + 1) / 2), odd(q.size() / 2);
		for (std::size_t i = 0; i < q.size(); ++i) (i & 1 ? odd : even)[i / 2] = q[i];
		for (std::size_t i = 1; i < q.size(); i += 2) q[i] = -q[i];
		F numerator = F::multiply(p, q);
		q = F::multiply(even, even), odd = F::multiply(odd, odd);
		p.resize((numerator.size() + 1 - std::size_t(k & 1)) / 2);
		for (std::size_t i = 0; i < p.size(); ++i) p[i] = numerator[2 * i + std::size_t(k & 1)];
		if (q.size() == odd.size()) q.push_back(T(0));
		for (std::size_t i = 0; i < odd.size(); ++i) q[i + 1] -= odd[i];
		p.shrink();
		k >>= 1;
	}
	return static_cast<unsigned long long>(k) < p.size() ? p[std::size_t(k)] / q[0] : T(0);
}

template<class T>
T linear_recurrence(const std::vector<T> &initial, const std::vector<T> &coefficients, long long k) {
	using F = LightFormalPowerSeries<T>;
	assert(k >= 0 && initial.size() == coefficients.size());
	const std::size_t n = initial.size();
	if (static_cast<unsigned long long>(k) < n) return initial[std::size_t(k)];
	if (!n) return T(0);
	F q(n + 1);
	q[0] = T(1);
	for (std::size_t i = 0; i < n; ++i) q[i + 1] = -coefficients[i];
	F p = F::multiply(F(initial.begin(), initial.end()), q).pre(static_cast<int>(n));
	return bostan_mori(std::move(p), std::move(q), k);
}

template<class T>
std::vector<T> multipoint_eval(const LightFormalPowerSeries<T> &f, const std::vector<T> &xs) {
	if (f.size() <= 32 || xs.size() <= 32) {
		std::vector<T> result;
		result.reserve(xs.size());
		for (T x : xs) result.push_back(f.eval(x));
		return result;
	}
	return fps_light_detail::ProductTree<T>(xs).evaluate(f);
}

template<class T>
LightFormalPowerSeries<T> interpolate(const std::vector<T> &xs, const std::vector<T> &ys) {
	assert(xs.size() == ys.size());
	return fps_light_detail::ProductTree<T>(xs).interpolate(ys);
}
}

#endif
Back to top page