convolution_ll2

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

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

概要

係数積が小さいときの畳み込み (2 つの NTT + CRT)

MOD1 $= 754974721$ と MOD3 $= 469762049$ の 2 素数だけで畳み込み、 CRT で復元する。NTT が 1 回少ない分 convolution_ll より速い。

パラメータ

戻り値

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

計算量

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

注意

• 真値が MOD1 * MOD3（約 $3.5 \times 10^{17}$）未満であること。畳み込み長 $L$ について 各係数は高々 $(\max |a_i|)(\max |b_j|) L$ になるので、これがこの上限を超えない 範囲でのみ使う（例: 各係数が $10^5$ 未満なら長さ $2^{24}$ まで安全）。 係数は非負であること（CRT 復元は $[0, \mathrm{MOD1} \cdot \mathrm{MOD3})$ を返す）。

備考

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

関連項目

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