疎 FPS の項収集・演算種別

components/fps_sparse_terms.hpp · GitHub で見る

共通ページ

fps_detail::SparseTerms は、通常版と軽量版の疎 FPS が共有する内部部品です。

Series は vector<mint>、Terms は次数と係数の vector<pair<int,mint>> です。Kind は逆数・対数・指数・冪の演算種別を表します。

collect(f,size,n,limit) は次数 1 以上 min(size,n) 未満の非零項を昇順で返します。定数項は含めず、項数が limit を超えた時点で走査を終了します。

走査する係数数を \(m\)、収集した項数を \(k\) として、時間は \(O(m)\)、追加空間は \(O(k)\) です。

依存ライブラリ

• modint998244353

検証コード

• test/convolution.test.cpp
• test/fps_bostan_mori.test.cpp
• 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_divmod.test.cpp
• test/fps_exp.test.cpp
• test/fps_exp_sparse.test.cpp
• test/fps_interpolate.test.cpp
• test/fps_inv.test.cpp
• test/fps_inv_sparse.test.cpp
• test/fps_light_compose.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_rational_coefficients.test.cpp
• test/fps_light_sqrt.test.cpp
• test/fps_light_taylor_shift.test.cpp
• test/fps_linear_recurrence.test.cpp
• test/fps_log.test.cpp
• test/fps_log_sparse.test.cpp
• test/fps_pow.test.cpp
• test/fps_pow_sparse.test.cpp
• test/fps_rational_coefficients.test.cpp
• test/fps_sqrt.test.cpp
• test/fps_sqrt_sparse.test.cpp
• test/fps_taylor_shift.test.cpp
• test/multipoint_eval.test.cpp
• test/online_convolution_light.test.cpp
• test/polynomial_inv_mod.test.cpp
• test/power_projection.test.cpp

コード

#ifndef FPS_SPARSE_TERMS_HPP
#define FPS_SPARSE_TERMS_HPP

#include "../math/mint.hpp"
#include <algorithm>
#include <cassert>
#include <numeric>
#include <utility>
#include <vector>

namespace fps_detail {
struct SparseTerms {
	using Series = std::vector<mint>;
	using Terms = std::vector<std::pair<int, mint>>;
	enum class Kind { inverse, logarithm, exponential, power };
	static Terms collect(const mint *f, int size, int n, int limit = 12) {
		Terms terms;
		for (int i = 1; i < std::min(size, n) && int(terms.size()) <= limit; ++i)
			if (f[i] != mint(0)) terms.emplace_back(i, f[i]);
		return terms;
	}
};
}
#endif

Back to top page