bostan_mori

関数 · きたまさ法（任意可換環版、$O(k^2 \log n)$）

template <internal::static_modint_c mint>
mint bostan_mori(std::vector<mint> p, std::vector<mint> q, std::int64_t n);

概要

Bostan-Mori 法

有理形式的冪級数 $p(x)/q(x)$ の $x^n$ の係数を $O(M(d) \log n)$ で求める （$d = \deg q$、$M$ はサイズ $d$ の畳み込みコスト）。各ステップで $q(-x)$ の順変換を 共有し、AVX2 が使える NTT-friendly な mint なら Montgomery + AVX2 NTT を使う。

テンプレートパラメータ

パラメータ

戻り値

mint $p(x)/q(x)$ の $x^n$ の係数

計算量

• 多項式次数を $d$ として $O(d \log d \log n)$

関連項目

• kitamasa — きたまさ法（任意可換環版、$O(k^2 \log n)$）
• kth_term — 線形漸化式の第 $n$ 項（NTT 版、$O(M(d) \log n)$）