convolution_fft_square

template <internal::static_modint_c mint>
std::vector<mint> convolution_fft_square(std::vector<mint> a);

概要

自乗畳み込み (a と a の畳み込み)。順変換が 1 回で済むため通常の 3 NTT に対し 2 NTT で計算できる。

middle_product_fft — 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_mod_constants — 任意 mod / 任意係数の畳み込みで使う 3 つの NTT-friendly 素数と Garner 法用の定数。 $\mathrm{MOD1} < \mathrm{MOD2} < \mathrm{MOD3}$ で、いずれも $2^{24}$ まで NTT 可能（最小は MOD1 の $2^{24}$）。