convolution_mod
template <unsigned int mod = 998244353, std::integral T>
std::vector<T> convolution_mod(const std::vector<T> &a, const std::vector<T> &b);
概要
任意 mod 畳み込み (3 つの NTT + Garner 法)
3 つの NTT-friendly 素数で畳み込み、Garner 法で復元した値を mod で取る。 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)$
注意
- 各係数は $[0, \mathrm{mod})$ の非負整数であること。Garner 復元値を mod で割った 剰余を返すため、負値や mod 以上の値を渡すと正しい結果にならない (真値を mod 還元したい場合は convolution_ll を使うこと)。
備考
- 畳み込み後の長さは $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_ll2— 係数積が小さいときの畳み込み (2 つの NTT + CRT)