convolution_avx2
関数 · Montgomery + AVX2 による NTT 畳み込み (NTT-friendly な 32bit 素数 mod 専用)
// (1)
template <unsigned int mod = 998244353, std::integral T>
std::vector<T> convolution_avx2(const std::vector<T> &a, const std::vector<T> &b);
// (2)
template <internal::static_modint_c mint>
std::vector<mint> convolution_avx2(const std::vector<mint> &a, const std::vector<mint> &b);
概要
(1) Montgomery + AVX2 による NTT 畳み込み (NTT-friendly な 32bit 素数 mod 専用)
値を [0, 2*mod) の Montgomery 表現で 8 レーン (u32x8) 同時に処理する。 通常の convolution より定数倍が小さい（$\mathrm{mod} = 998244353$、$N = 2^{20}$ で約 1.5 倍速）。 AVX2 が使えない CPU では実行時に通常の convolution へフォールバックする。
- テンプレートパラメータ
mod: NTT-friendly な素数 mod (既定: 998244353) - テンプレートパラメータ
T: 整数型 (std::integral) - パラメータ
a: 入力多項式の係数列 - パラメータ
b: 入力多項式の係数列 - 戻り値:
std::vector<T>a と b の畳み込みを mod で取った値 (長さ a.size() + b.size() - 1) - 計算量: 出力長を $N$ として $O(N\log N)$
- 備考:
modは $2 < \mathrm{mod} < 2^{30}$ の NTT-friendly 素数であること（Montgomery 簡約・ 遅延簡約の桁あふれ回避のため $2^{30}$ 未満を要求）。
(2) Montgomery + AVX2 による NTT 畳み込み (static_modint 版)
- テンプレートパラメータ
mint: NTT-friendly な static modint（$\mathrm{mod} < 2^{30}$） - パラメータ
a: 入力多項式の係数列 - パラメータ
b: 入力多項式の係数列 - 戻り値:
std::vector<mint>a と b の畳み込み (長さ a.size() + b.size() - 1) - 計算量: 出力長を $N$ として $O(N\log N)$