Algoogle

Algorithm for Programming Contest

高速フーリエ変換

基本情報


計算量
用途 フーリエ変換する

N := 変換する列の長さ(2冪)

invを指定すると逆変換

解説


以下の離散フーリエ変換の正変換と逆変換をする.
結構誤差る

畳み込みを利用したいときに使うことが多い
fとgは周期Nの周期関数とすると

畳み込みを使うと多項式f, gの掛け算が以下のようにかける

コード


(fft.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
typedef complex<double> cd;
vector<cd> fft(vector<cd> f, bool inv) {
    int n, N = f.size();
    for(n=0;;n++) if(N == (1<<n)) break;
    for (int m = 0; m < N; m++) {
        int m2 = 0;
        for(int i = 0; i < n; i++) if(m&(1<<i)) m2 |= (1<<(n-1-i));
        if(m < m2) swap(f[m], f[m2]);
    }

    for(int t=1;t<N;t*=2) {
        double theta = acos(-1.0) / t;
        cd w(cos(theta), sin(theta));
        if(inv) w = cd(cos(theta), -sin(theta));
        for(int i=0;i<N;i+=2*t){
            cd power(1.0, 0.0);
            for (int j = 0; j < t; j++) {
                cd tmp1 = f[i+j] + f[i+t+j] * power;
                cd tmp2 = f[i+j] - f[i+t+j] * power;
                f[i+j] = tmp1;
                f[i+t+j] = tmp2;
                power = power * w;
            }
        }
    }
    if(inv) for(int i = 0; i < N; i++) f[i] /= N;
    return f;
}

問題


Comments