看完學(xué)會(huì)速傅立葉變換FFT

FFT 即快速傅立葉變換。在很多計(jì)算機(jī)領(lǐng)域都用用處，例如數(shù)字圖像處理、計(jì)算機(jī)網(wǎng)絡(luò)。但他在算法競(jìng)賽中主要是用于多項(xiàng)式和生成函數(shù)相關(guān)的題目。

多項(xiàng)式

表達(dá)方式

簡(jiǎn)介

• 系數(shù)表達(dá)式，即。
• 坐標(biāo)形式。每一個(gè)坐標(biāo)用表示。顯然，為了能夠表示一個(gè)確定的多項(xiàng)式，需要個(gè)不同的坐標(biāo)來(lái)表示。

比較

• 對(duì)于系數(shù)表示，多項(xiàng)式加法的時(shí)間復(fù)雜度是，多項(xiàng)式乘法的時(shí)間復(fù)雜度是。
• 對(duì)于點(diǎn)值表示，多項(xiàng)式加法的時(shí)間復(fù)雜度同樣是，但是乘法的時(shí)間復(fù)雜度就是（因?yàn)槎囗?xiàng)式乘法以后最高項(xiàng)次數(shù)為，我們只需要個(gè)坐標(biāo)表示）。

思考

這樣一來(lái)，我們就有一個(gè)想法，多項(xiàng)式乘法，是不是可以利用坐標(biāo)表示做多項(xiàng)式乘法特別快這點(diǎn)來(lái)優(yōu)化算法。

于是需要解決的最大的問(wèn)題就是，多項(xiàng)式兩種表示方法之間的互相轉(zhuǎn)換。

求值樸素做法的時(shí)間復(fù)雜度是，即隨便選取一個(gè)值帶入，暴力計(jì)算。

差值樸素的做法時(shí)間復(fù)雜度是，即根據(jù)坐標(biāo)進(jìn)行高斯消元。

在介紹 FFT 之前，得先學(xué)習(xí) DFT （離散傅里葉變換）算法。

DFT

由于對(duì)一個(gè)多項(xiàng)式的點(diǎn)值表達(dá)式的取是任意的，所以好的取法可能會(huì)使一個(gè)算法產(chǎn)生本質(zhì)性的蛻變。

我們選取次單位復(fù)根作為來(lái)取值。

單位復(fù)根

，這個(gè)方程的復(fù)數(shù)根為次單位根。

單位的個(gè)單位根分別為。

個(gè)單位根在復(fù)平面的坐標(biāo)表示為，我們將這個(gè)記為。在復(fù)平面上形象的表示的話，就是下圖：

單位根在多項(xiàng)式的應(yīng)用

我們將個(gè)單位根帶入多項(xiàng)式可以得到個(gè)因變量結(jié)果，記為。

我們將個(gè)單位根的倒數(shù)作為自變量帶入由作為系數(shù)的多項(xiàng)式，可以得到。

而當(dāng)?shù)臅r(shí)候，它為，其余時(shí)候，它為（通過(guò)等比數(shù)列求和）。于是有。

于是可以發(fā)現(xiàn)，將個(gè)單位根的倒數(shù)帶入變換后的多項(xiàng)式，可以得到原來(lái)的多項(xiàng)式。

這樣一來(lái)，我們利用個(gè)單位根的性質(zhì)，完成了多項(xiàng)式兩種表示方式之間的轉(zhuǎn)換。

DFT算法

有了的取值，我們就可以得到的取值了。

。

直接暴力計(jì)算，兩個(gè)方向轉(zhuǎn)換的時(shí)間復(fù)雜均為。

FFT

那么 FFT 算法是如何優(yōu)化計(jì)算這一過(guò)程的？利用分治。

我們把一個(gè)多項(xiàng)式的計(jì)算分為偶數(shù)項(xiàng)的計(jì)算和奇數(shù)項(xiàng)的計(jì)算：

也就是說(shuō)， FFT 的思想就是不斷得把一個(gè)多項(xiàng)式拆分成奇數(shù)多項(xiàng)式和偶數(shù)多項(xiàng)式，然后合并兩個(gè)多項(xiàng)式的信息。

也就是說(shuō)，如果我們已經(jīng)得到了和，我們只需要就可以得到了。

每次都能把多項(xiàng)式的長(zhǎng)度減小一半，于是時(shí)間復(fù)雜度就是。

模版

C++ 是自帶了復(fù)數(shù) stl 的，即：

#include

但是常數(shù)大，跑得慢，不如自己重載的好。

• 下面的模版必須要保證是的整數(shù)次冪。

typedef double LD;
const LD PI = acos(-1);
struct C {
    LD r, i;
    C(LD r = 0, LD i = 0): r(r), i(i) {}
};
C operator + (const C& a, const C& b) {
    return C(a.r + b.r, a.i + b.i);
}
C operator - (const C& a, const C& b) {
    return C(a.r - b.r, a.i - b.i);
}
C operator * (const C& a, const C& b) {
    return C(a.r * b.r - a.i * b.i, a.r * b.i + a.i * b.r);
}

void FFT(C x[], int n, int p) {
    for (int i = 0, t = 0; i < n; ++i) {
        if (i > t) swap(x[i], x[t]);
        for (int j = n >> 1; (t ^= j) < j; j >>= 1);
    }
    for (int h = 2; h <= n; h <<= 1) {
        C wn(cos(p * 2 * PI / h), sin(p * 2 * PI / h));
        for (int i = 0; i < n; i += h) {
            C w(1, 0), u;
            for (int j = i, k = h >> 1; j < i + k; ++j) {
                u = x[j + k] * w;
                x[j + k] = x[j] - u;
                x[j] = x[j] + u;
                w = w * wn;
            }
        }
    }
    if (p == -1)
        FOR (i, 0, n)
            x[i].r /= n;
}

void conv(C a[], C b[], int n) {
    FFT(a, n, 1);
    FFT(b, n, 1);
    FOR (i, 0, n)
        a[i] = a[i] * b[i];
    FFT(a, n, -1);
}

例題

A * B II

https://acm.ecnu.edu.cn/problem/3007/

大整數(shù)相乘。

把每一位都看成是多項(xiàng)式其中一項(xiàng)的系數(shù)，那么大數(shù)最后的結(jié)果也就是多項(xiàng)式乘法系數(shù)的結(jié)果。

要進(jìn)位處理。

Hnoi2017 禮物

顯然是要計(jì)算的最小值，其中$0≤x

展開(kāi)這個(gè)式子，

除了，其他的和與相關(guān)的項(xiàng)都可以在的時(shí)間內(nèi)算出了

那么配個(gè)方，就可以求出最小值了，而是固定的

現(xiàn)在的問(wèn)題就是求，我們可以用FFT來(lái)解決

如果我們把多項(xiàng)式倒置，我們就能發(fā)現(xiàn)式子的和的下標(biāo)和可以相同，我們可以利用多項(xiàng)式乘法同時(shí)算出卷積。

設(shè)，那么，這樣就可以用FFT算出來(lái)了

總的時(shí)間復(fù)雜度

#include
#define inf 0x3fffffff
using namespace std;

typedef double LD;
const LD PI=acos(-1);
struct C
{
    LD r,i;
    C(LD r=0,LD i=0):r(r),i(i){}
};
C operator + (const C& a, const C& b){
    return C(a.r+b.r,a.i+b.i);
}
C operator - (const C& a, const C& b){
    return C(a.r-b.r,a.i-b.i);
}
C operator * (const C& a, const C& b){
    return C(a.r*b.r-a.i*b.i,a.r*b.i+a.i*b.r);
}
 
void FFT(C x[],int n,int p)
{
    for (int i=0,t=0;i