kitamasa
関数 · きたまさ法（任意可換環版、$O(k^2 \log n)$）
template <class T>
T kitamasa(const std::vector<T> &a, const std::vector<T> &d, std::int64_t n);
概要
きたまさ法（任意可換環版、$O(k^2 \log n)$）
線形漸化式 $a_i = \sum_{j=1}^{k} d_j a_{i-j}$（$i \ge k$）の第 $n$ 項を、 特性多項式 $f(x) = x^k - \sum_j d_j x^{k-1-j}$ を法とした $x^n \bmod f$ の 二乗法で求める。任意の可換環 T に対応（NTT 非対応 mod・dynamic_modint・ 行列・有理数など畳み込みできない環でも可）。NTT-friendly な static_modint で $O(M(k) \log n)$ が欲しい場合は同ファイルの kth_term を使う。
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
T |
可換環（加減乗算と T(0)/T(1) を持つ） |
パラメータ
| 名前 | 説明 |
|---|---|
a |
初項 $a_0, \ldots, a_{k-1}$ |
d |
漸化式の係数 $d_1, \ldots, d_k$（$a_i = d_1 a_{i-1} + \cdots + d_k a_{i-k}$） |
n |
求める項の番号 |
戻り値
T $a_n$
計算量
- 漸化式の次数を $k$ として $O(k^2 \log n)$
関連項目
bostan_mori— Bostan-Mori 法kth_term— 線形漸化式の第 $n$ 項（NTT 版、$O(M(d) \log n)$）