middle_product_fft
関数 · internal/internal_fft.hpp
template <internal::static_modint_c mint>
std::vector<mint> middle_product_fft(std::vector<mint> a, std::vector<mint> b);
概要
middle product (転置乗算): a（長さ $n$）と b（長さ $m \le n$）に対し $c_i = \sum_{j=0}^{m-1} a_{i+j} b_j$（$i = 0, \ldots, n-m$）を返す（長さ $n-m+1$）。 これは a と $\mathrm{rev}(b)$ のフル積 $a \cdot \mathrm{rev}(b)$ の添字 $m-1, \ldots, n-1$ にあたる。 サイズ $\mathrm{bit\_ceil}(n)$ の巡回畳み込み 1 回で求まる。$z \ge n$ より該当範囲には巻き込みが起きない。
関連項目
convolution_fft_square— 自乗畳み込み (a と a の畳み込み)。順変換が 1 回で済むため通常の 3 NTT に対し 2 NTT で計算できる。convolution_mod_constants— 任意 mod / 任意係数の畳み込みで使う 3 つの NTT-friendly 素数と Garner 法用の定数。 $\mathrm{MOD1} < \mathrm{MOD2} < \mathrm{MOD3}$ で、いずれも $2^{24}$ まで NTT 可能（最小はMOD1の $2^{24}$）。