kth_term
関数 · きたまさ法（任意可換環版、$O(k^2 \log n)$）
template <internal::static_modint_c mint>
mint kth_term(std::vector<mint> a, std::vector<mint> c, std::int64_t n);
概要
線形漸化式の第 $n$ 項（NTT 版、$O(M(d) \log n)$）
$a_i = \sum_{j=1}^{d} c_j a_{i-j}$（$i \ge d$）の第 $n$ 項を Bostan-Mori 法で求める。 NTT-friendly な static_modint 専用。畳み込みできない環では kitamasa を使う。
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
mint |
NTT-friendly な static modint |
パラメータ
| 名前 | 説明 |
|---|---|
a |
初項 $a_0, \ldots, a_{d-1}$ |
c |
漸化式の係数 $c_1, \ldots, c_d$ |
n |
求める項の番号 |
戻り値
mint $a_n$
計算量
- 漸化式の次数を $d$ として $O(d \log d \log n)$
関連項目
kitamasa— きたまさ法（任意可換環版、$O(k^2 \log n)$）bostan_mori— Bostan-Mori 法