convolution_mod
関数 · FFT・実数畳み込み
template <std::integral T>
std::vector<T> convolution_mod(const std::vector<T> &a, const std::vector<T> &b, T mod);
概要
任意 mod 畳み込み（実数 FFT を 15bit 分割で 3 回適用）
係数を上位 15bit / 下位 15bit に分けて $a = a_1 \cdot 2^{15} + a_0$ とし、 $a_1 b_1$、$a_0 b_0$、$(a_1 + a_0)(b_1 + b_0)$ の 3 回の畳み込みから復元する。 double の精度の範囲（$\mathrm{mod}^2 \times$ 長さ が約 $2^{53}$ 以下）で正しい。
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
T |
整数型 |
パラメータ
| 名前 | 説明 |
|---|---|
a |
入力多項式の係数列（$[0, \mathrm{mod})$ を想定） |
b |
入力多項式の係数列 ([0, mod) を想定) |
mod |
出力を取る法 (NTT-friendly でなくてよい) |
戻り値
std::vector<T> a と b の畳み込みを mod で取った値 (長さ a.size() + b.size() - 1)
計算量
- 出力長を $N$ として $O(N\log N)$
関連項目
FFT_MAX_LOG— FFT で扱える最大長は $2^{\mathrm{FFT\_MAX\_LOG}}$。_fft— 複素 FFT (in-place, 反復 Cooley-Tukey)convolution— FFT による畳み込み