convolution

関数 · NTT・畳み込み (convolution)

// (1)
template <internal::static_modint_c mint>
std::vector<mint> convolution(const std::vector<mint> &a, const std::vector<mint> &b);

// (2)
template <unsigned int mod = 998244353, std::integral T>
std::vector<T> convolution(const std::vector<T> &a, const std::vector<T> &b);

概要

(1) NTT による畳み込み (modint 版)

• テンプレートパラメータ mint: NTT-friendly な static modint (mod - 1 が畳み込み長で割り切れること)
• パラメータ a: 入力多項式の係数列
• パラメータ b: 入力多項式の係数列
• 戻り値: std::vector<mint> a と b の畳み込み (長さ a.size() + b.size() - 1)
• 計算量: 出力長を $N$ として $O(N \log N)$

(2) NTT による畳み込み (整数版)

• テンプレートパラメータ 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)$
• 備考: 各係数は modint コンストラクタを通して mod で正規化される (負値も可)。

関連項目

• CONVOLUTION_NAIVE_THRESHOLD — 愚直畳み込みへ切り替える入力サイズの閾値
• convolution_square — 自乗畳み込み (a と a の畳み込み, modint 版)
• middle_product — middle product / 転置乗算（modint 版）
• convolution_ll — 任意係数の畳み込み (3 つの NTT + Garner 法)
• convolution_ll2 — 係数積が小さいときの畳み込み (2 つの NTT + CRT)
• convolution_mod — 任意 mod 畳み込み (3 つの NTT + Garner 法)