middle_product
template <internal::static_modint_c mint>
std::vector<mint> middle_product(const std::vector<mint> &a, const std::vector<mint> &b);
概要
middle product / 転置乗算（modint 版）
a（長さ $n$）と b（長さ $m \le n$）に対し $c_i = \sum_j a_{i+j} b_j$ （$i = 0, \ldots, n-m$）を返す（長さ $n-m+1$）。a と $\mathrm{rev}(b)$ のフル積の 中央部に等しく、変換長が $\mathrm{bit\_ceil}(n)$ で済む。多項式補間・分割統治など 「ずらし内積」が要る場面で使う。
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
mint |
NTT-friendly な static modint |
パラメータ
| 名前 | 説明 |
|---|---|
a |
長さ $n$ の係数列 |
b |
長さ $m$（$m \le n$）の係数列 |
戻り値
std::vector<mint> $c_i = \sum_j a_{i+j} b_j$（長さ $n-m+1$）
計算量
- $n = |a|$ として $O(n \log n)$
関連項目
CONVOLUTION_NAIVE_THRESHOLD— 愚直畳み込みへ切り替える入力サイズの閾値convolution— NTT による畳み込み (modint 版)convolution_square— 自乗畳み込み (a と a の畳み込み, modint 版)convolution_ll— 任意係数の畳み込み (3 つの NTT + Garner 法)convolution_ll2— 係数積が小さいときの畳み込み (2 つの NTT + CRT)convolution_mod— 任意 mod 畳み込み (3 つの NTT + Garner 法)