convolution.hpp ファイル

#include "../../kyopro_library/template.hpp"

[ソースコード]

関数
void	FFT (vector< complex< double > > &a, bool inv=false)
	高速フーリエ変換
vector< double >	Convolve (const vector< double > &a, const vector< double > &b)
	畳み込み

関数詳解

FFT()

void FFT	(	vector< complex< double > > &	a,
		bool	inv = false )

高速フーリエ変換

覚え書き

O(N log(N))

f(x) = Σ a[i]x^i, w^N = 1 とすると、F(t) = Σ f(w^i)t^i の各係数を返す。

a = (a[0], a[1], ..., a[n-1]) -> fa = (f(w^0), f(w^1), ..., f(w^(n-1)))

convolution.hpp の 7 行目に定義があります。

Convolve()

vector< double > Convolve	(	const vector< double > &	a,
		const vector< double > &	b )

畳み込み

覚え書き

O(N log(N))

convolution.hpp の 36 行目に定義があります。