convolution_ll

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

std::vector<std::int64_t> convolution_ll(const std::vector<std::int64_t> &a, const std::vector<std::int64_t> &b);

概要

任意係数の畳み込み (3 つの NTT + Garner 法)

3 つの NTT-friendly 素数で畳み込み、Garner 法で復元することで オーバーフローしない範囲の int64_t 畳み込みを求める。

パラメータ

戻り値

std::vector<std::int64_t> a と b の畳み込み (長さ a.size() + b.size() - 1)

計算量

• 出力長を $N$ として $O(N \log N)$

備考

• 畳み込み後の長さは $2^{24}$（約 $1.6 \times 10^7$）以下でなければならない。

関連項目

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