有理 FPS の区間係数取得（高速版）

fps/rational_fps_coefficients.hpp · GitHub で見る

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

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

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

#include "lib/fps/rational_fps_coefficients.hpp"

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

操作	内容・返り値	計算量
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 の fps で、a[i] は \([x^{l+i}]p(x)/q(x)\) です。l==r なら空の FPS を返し、係数が 0 の部分も省略しません。

係数型は fps と同じ法 998244353 の modint です。p[i]・q[i] は \(x^i\) の係数で、q は空でなく q[0]!=0 としてください。分子の次数が分母以上でも、q[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 で渡せます。

初期値と漸化式の係数から使う場合は、次のように分子と分母を作ります。

#include "lib/fps/rational_fps_coefficients.hpp"

std::vector<mint> initial{0, 1}, coefficients{1, 1};
int d = initial.size();
fps q(d + 1);
q[0] = 1;
for (int i = 0; i < d; ++i) q[i + 1] = -coefficients[i];
fps p = fps::multiply(fps(initial), q).pre(d);
auto a = rational_fps_coefficients(p, q, 10, 15);
// {55, 89, 144, 233, 377}

初期値と係数列の長さは同じにし、coefficients[0] に 1 つ前の項の係数を入れます。1 項だけなら Bostan–Mori や 線形漸化式の第 k 項 も使えます。

MSB-first 版 Bostan–Mori を使います。時間は \(O(N\log N\log r+(N+M)\log(N+M))\)、追加空間は \(O(N\log r+M)\) です。先頭付近の取得は \(O((N+M)\log(N+M))\) 時間です。

参考：AtCoder Algorithm Lectures：Bostan–Mori の発展

依存ライブラリ

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

検証コード

• test/fps_rational_coefficients.test.cpp

コード

#ifndef CP_FPS_RATIONAL_FPS_COEFFICIENTS_HPP
#define CP_FPS_RATIONAL_FPS_COEFFICIENTS_HPP

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

namespace fps_detail {
struct CoefficientRangeTransform {
	using O = Operations<mint>;
	static void forward(fps &f) { O::ntt(f); }
	static void inverse(fps &f) { O::intt(f); }
	static void product(fps &f, const fps &g) { O::pointwise(f, f, g, int(f.size())); }
};
}

template <class T>
FormalPowerSeries<T> rational_fps_coefficients(FormalPowerSeries<T> p, FormalPowerSeries<T> q, long long l, long long r) {
	using O = fps_detail::Operations<T>;
	if constexpr (!std::is_same_v<T, mint>)
		return O::export_work(rational_fps_coefficients(O::import_work(p), O::import_work(q), l, r));
	else return rational_fps_detail::Coefficients<fps, fps_detail::CoefficientRangeTransform>::get(std::move(p), std::move(q), l, r);
}

#endif

Back to top page