convolution_square
template <internal::static_modint_c mint>
std::vector<mint> convolution_square(const std::vector<mint> &a);
概要
自乗畳み込み (a と a の畳み込み, modint 版)
a を自身と畳み込む。順変換を 1 回に削減できるため convolution(a, a) より速い。
テンプレートパラメータ
| 名前 | 説明 |
|---|---|
mint |
NTT-friendly な static modint |
パラメータ
| 名前 | 説明 |
|---|---|
a |
入力多項式の係数列 |
戻り値
std::vector<mint> a と a の畳み込み (長さ 2 * a.size() - 1)
計算量
- 出力長を $N$ として $O(N \log N)$
関連項目
CONVOLUTION_NAIVE_THRESHOLD— 愚直畳み込みへ切り替える入力サイズの閾値convolution— NTT による畳み込み (modint 版)middle_product— middle product / 転置乗算（modint 版）convolution_ll— 任意係数の畳み込み (3 つの NTT + Garner 法)convolution_ll2— 係数積が小さいときの畳み込み (2 つの NTT + CRT)convolution_mod— 任意 mod 畳み込み (3 つの NTT + Garner 法)