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

多項式

表達方式

簡介

• 系數(shù)表達式，即。
• 坐標形式。每一個坐標用表示。顯然，為了能夠表示一個確定的多項式，需要個不同的坐標來表示。

比較

• 對于系數(shù)表示，多項式加法的時間復(fù)雜度是，多項式乘法的時間復(fù)雜度是。
• 對于點值表示，多項式加法的時間復(fù)雜度同樣是，但是乘法的時間復(fù)雜度就是（因為多項式乘法以后最高項次數(shù)為，我們只需要個坐標表示）。

思考

這樣一來，我們就有一個想法，多項式乘法，是不是可以利用坐標表示做多項式乘法特別快這點來優(yōu)化算法。

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

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

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

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

DFT

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

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

單位復(fù)根

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

單位的個單位根分別為。

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

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

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

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

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

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

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

DFT算法

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

。

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

FFT

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

我們把一個多項式的計算分為偶數(shù)項的計算和奇數(shù)項的計算：

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

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

每次都能把多項式的長度減小一半，于是時間復(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ù)相乘。

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

要進位處理。

Hnoi2017 禮物

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

展開這個式子，

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

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

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

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

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

總的時間復(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