有理 FPS の区間係数取得（軽量実装）

fps/rational_fps_coefficients_light.hpp · GitHub で見る

共通ページ · 軽量実装

有理 FPS の区間係数取得の高速実装はこちら

軽量 FPS を使い、有理式で表された FPS の連続する係数をまとめて求めます。

#include "lib/fps/rational_fps_coefficients_light.hpp"

light_fps p{1}, q{1, -1, -1};
auto a = light_fps_algorithms::rational_fps_coefficients(p, q, 10, 15);
// {89, 144, 233, 377, 610}

操作	内容・返り値	計算量
light_fps_algorithms::rational_fps_coefficients(p,q,l,r)	\(p(x)/q(x)\) の \(x^l,x^{l+1},\ldots,x^{r-1}\) の係数を順に返す	\(O(N\log N\log r+(N+M)\log(N+M))\)

区間は右端を含まない [l,r) です。返り値は長さ r-l の LightFormalPowerSeries<T> で、a[i] は \([x^{l+i}]p(x)/q(x)\) です。空区間には空の FPS を返し、係数が 0 の部分も残します。

係数型は法 998244353 の modint です。q は空でなく q[0]!=0 としてください。分子の次数が分母以上でも、分母の定数項が 1 でなくても使えます。

l,r は long long で \(0\le l\le r\) とし、\(N=\max(\lvert p\rvert,\lvert q\rvert)\)、\(M=r-l\) に対して \(N+M\le2^{22}\) としてください。開始位置が大きい区間にも対応します。引数は値渡しなので std::move も使えます。

初期値と漸化式からの使い方は 通常版の説明 を参照してください。fps を light_fps、関数名を light_fps_algorithms::rational_fps_coefficients に置き換えます。

時間は \(O(N\log N\log r+(N+M)\log(N+M))\)、追加空間は \(O(N\log r+M)\) です。先頭付近の取得は \(O((N+M)\log(N+M))\) 時間です。

依存ライブラリ

• 軽量 FPS の共通実装
• 軽量 FPS の基本演算
• 軽量 FPS の NTT
• 軽量 FPS の疎演算
• 疎 FPS の項収集・演算種別
• 多項式の積・打ち切り積の共通処理
• 多項式の共通積木
• 有理 FPS の区間係数取得の共通処理
• 軽量な形式的冪級数
• modint998244353

検証コード

• test/fps_light_rational_coefficients.test.cpp

コード

#ifndef CP_FPS_RATIONAL_FPS_COEFFICIENTS_LIGHT_HPP
#define CP_FPS_RATIONAL_FPS_COEFFICIENTS_LIGHT_HPP

#include "fps_light.hpp"
#include "../components/rational_fps_coefficients.hpp"

namespace fps_light_detail {
struct CoefficientRangeTransform {
	static void forward(light_fps &f) { transform(f); }
	static void inverse(light_fps &f) { transform(f, true); }
	static void product(light_fps &f, const light_fps &g) { pointwise(f, g); }
};
}

namespace light_fps_algorithms {
template <class T>
LightFormalPowerSeries<T> rational_fps_coefficients(LightFormalPowerSeries<T> p, LightFormalPowerSeries<T> q, long long l, long long r) {
	if constexpr (!std::is_same_v<T, mint>) {
		light_fps a(p.size()), b(q.size());
		for (std::size_t i = 0; i < p.size(); ++i) a[i] = mint::raw(p[i].val());
		for (std::size_t i = 0; i < q.size(); ++i) b[i] = mint::raw(q[i].val());
		a = rational_fps_coefficients(std::move(a), std::move(b), l, r);
		LightFormalPowerSeries<T> result(a.size());
		for (std::size_t i = 0; i < a.size(); ++i) result[i] = T::raw(a[i].val());
		return result;
	} else return rational_fps_detail::Coefficients<light_fps, fps_light_detail::CoefficientRangeTransform>::get(std::move(p), std::move(q), l, r);
}
}

#endif

Back to top page