多項式の積・打ち切り積の共通処理

components/polynomial_multiply.hpp · GitHub で見る

共通ページ

polynomial_detail::Products<F,Limit> は、積の木と FPS 合成が共有する内部部品です。F は F::multiply を持つ多項式型、Limit はその畳み込みの最大係数数です。

multiply(a,b) は通常の積、multiply_low(a,b,n) は積の低次 n 係数を返します。後者の返り値は長さ n で、不足分は 0 です。積が Limit を超える場合は係数列を分割して計算します。

分割しない場合の時間は F::multiply と同じです。分割する場合は、必要なブロック対ごとの畳み込み時間の合計と、係数の加算時間がかかります。追加空間は出力と各ブロックの作業領域に比例します。

検証コード

• test/fps_compose.test.cpp
• test/fps_compose_large.test.cpp
• test/fps_compositional_inverse.test.cpp
• test/fps_compositional_inverse_large.test.cpp
• test/fps_interpolate.test.cpp
• test/fps_light_compose.test.cpp
• test/fps_light_compose.test.cpp
• test/fps_light_compositional_inverse.test.cpp
• test/fps_light_compositional_inverse.test.cpp
• test/fps_light_convolution.test.cpp
• test/fps_light_divmod.test.cpp
• test/fps_light_exp.test.cpp
• test/fps_light_interpolate.test.cpp
• test/fps_light_inv.test.cpp
• test/fps_light_linear_recurrence.test.cpp
• test/fps_light_log.test.cpp
• test/fps_light_multipoint_eval.test.cpp
• test/fps_light_polynomial_extended_gcd.test.cpp
• test/fps_light_polynomial_gcd.test.cpp
• test/fps_light_polynomial_inv_mod.test.cpp
• test/fps_light_pow.test.cpp
• test/fps_light_power_projection.test.cpp
• test/fps_light_power_projection.test.cpp
• test/fps_light_rational_coefficients.test.cpp
• test/fps_light_sqrt.test.cpp
• test/fps_light_taylor_shift.test.cpp
• test/multipoint_eval.test.cpp
• test/online_convolution_light.test.cpp
• test/power_projection.test.cpp

コード

#ifndef CP_COMPONENTS_POLYNOMIAL_MULTIPLY_HPP
#define CP_COMPONENTS_POLYNOMIAL_MULTIPLY_HPP

#include <algorithm>
#include <cstddef>

namespace polynomial_detail {
template<class F, std::size_t Limit = 1U << 23>
struct Products {
	static_assert(Limit >= 2);
	static F multiply(const F& a, const F& b) {
		if (a.empty() || b.empty()) return {};
		const auto n = a.size() + b.size() - 1;
		return n <= Limit ? F::multiply(a, b) : multiply_low(a, b, n);
	}
	static F multiply_low(const F& a, const F& b, std::size_t n) {
		F result(n);
		constexpr std::size_t block = Limit / 2;
		for (std::size_t i = 0; i < std::min(a.size(), n); i += block)
			for (std::size_t j = 0; j < std::min(b.size(), n - i); j += block) {
				F x(a.begin() + i, a.begin() + std::min(i + block, a.size()));
				F y(b.begin() + j, b.begin() + std::min(j + block, b.size()));
				F p = F::multiply(x, y);
				for (std::size_t k = 0; k < std::min(p.size(), n - i - j); ++k)
					result[i + j + k] += p[k];
			}
		return result;
	}
};
}

#endif

Back to top page