convolution

関数 · FFT・実数畳み込み

template <class T>
requires std::is_arithmetic_v<T>
std::vector<T> convolution(const std::vector<T> &a, const std::vector<T> &b);

概要

FFT による畳み込み

テンプレートパラメータ

パラメータ

戻り値

std::vector<T> a と b の畳み込み (長さ 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_mod — 任意 mod 畳み込み（実数 FFT を 15bit 分割で 3 回適用）