FFT 學(xué)習(xí)筆記

\(\mathbf{Preview}\)

前置知識(shí)。

多項(xiàng)式表示法

系數(shù)表示法：就是正常的多項(xiàng)式表示方法。\(f(x) = \sum\limits_{i = 0}^{n - 1} a_i \times x^i\)。

點(diǎn)值表示法：如果我們知道 \(n\) 個(gè)數(shù) \(b_1, \cdots, b_n\)，這些數(shù)在帶入 \(f\) 多項(xiàng)式后他們的具體值 \(f(b_1), \cdots, f(b_n)\)，我們就可以通過這些值算出 \(f\)，因此 \(f\) 也可以用若干個(gè)點(diǎn)對(duì) \(\Big(b_1, f(b_1)\Big),\cdots,\Big(b_n, f(b_n)\Big)\) 來表示。¹

向量

向量是一個(gè)有方向，有長度的量，為了方便運(yùn)算，起點(diǎn)坐標(biāo)通常被設(shè)為原點(diǎn)。

但正如同剛才所說，向量的兩個(gè)關(guān)鍵因素為方向和長度，所以還可以用這一種方式：

這也被稱為 極角坐標(biāo)系， \(r\) 也被稱為向量的模長，\(\alpha\) 自然是與 \(x\) 軸成的夾角。

向量在坐標(biāo)系中大致是這樣：

由于在 FFT 中不是很重要，所以粗略介紹。

弧度制

一個(gè)點(diǎn)在一個(gè)以原點(diǎn)為中心半徑為 \(1\) 的圓上時(shí)，這個(gè)點(diǎn)與 \(x\) 軸的夾角在弧度制下被表示為這個(gè)點(diǎn)到圓與 \(x\) 軸的交點(diǎn)的圓弧長度。簡單來說，\(2\pi = 360\degree\)。

復(fù)數(shù)

設(shè) \(a,b\) 為實(shí)數(shù)，\(i^2 = -1\)，則形如 \(a+bi\) 的數(shù)被稱為復(fù)數(shù)。

在復(fù)平面中，\(x\) 軸表示實(shí)數(shù)，\(y\) 軸（除原點(diǎn)）表示虛數(shù)，從 \((0, 0)\to (a, b)\) 的向量表示 \(a+bi\)。

模長：表示 \(a+bi\) 向量的模長，即 \(\sqrt{a^2 + b^2}\)。

幅角：以逆時(shí)針為正方向，\(x\) 軸正方向到 \(a+bi\) 的向量形成的有向角。

加法運(yùn)算：\((a+bi)+(c+di) = (a+c)+(b+d)i\)

減法運(yùn)算：\((a+bi)-(c+di) = (a-c)+(b-d)i\)

乘法運(yùn)算：

• 幾何定義：復(fù)數(shù)相乘，模長相乘，幅角相加
• 代數(shù)定義：\((a+bi)\times (c+di) = (ac - bd) + (bc + ad)i\)。

除法定義在本文中不提及。

單位根

下文中，默認(rèn) \(n\) 為 \(2\) 的正整數(shù)次冪

以單位圓原點(diǎn)為起點(diǎn)，圓的 \(n\) 等分點(diǎn)為終點(diǎn)，做 \(n\) 個(gè)向量，設(shè)幅角為正且最小的向量對(duì)應(yīng)的復(fù)數(shù)為 \(w_n\)，稱為 \(n\) 次單位根。

根據(jù)復(fù)數(shù)乘法的運(yùn)算法則，其余 \(n - 1\) 個(gè)復(fù)數(shù)為 \(w_n^2, w_n^3,\cdots,w_n^{n}\)

注意 \(w_n^0 = w_n^n\)（對(duì)應(yīng)復(fù)平面上以 \(x\) 軸為正方向的向量，就是圖中的 \(u\)）

由歐拉公式，\(w_n^k = \cos k\dfrac{2\pi}{n}+i\sin{k\dfrac{2\pi}{n}}\)，且有 \(w_{2n}^{2k} = w_n^k,w_{n}^{k+\frac{n}{2}}=-w_{n}^k,w_n^0 = w_n^n = 1\)。

接下來進(jìn)入正題。

\(\mathbf{Part. 0 \ \ 思路}\)

首先，我們考慮如何計(jì)算兩個(gè)多項(xiàng)式 \(P, Q\) 的乘法，假設(shè)次數(shù)分別為 \(n - 1, m - 1\)，為了方便后面的分治，我們先把 \(P, Q\) 的長度擴(kuò)成一個(gè)大于 \(n + m\) 的 \(2\) 的冪次。設(shè)這個(gè)冪次為 \(l = 2^t\)。

顯然，在系數(shù)表示法中，我們只能 \(\mathcal{O}(n^2)\) 求乘法。

但是，如果我們能把 \(P, Q\) 都轉(zhuǎn)化成點(diǎn)值表示法，其中 \(P\) 的點(diǎn)值表示法為 \(\Big(x_1, P(x_1)\Big),\cdots,\Big(x_l, P(x_l)\Big)\)，\(Q\) 的點(diǎn)值表示法為 \(\Big(x_1, Q(x_1)\Big),\cdots,\Big(x_l, Q(x_l)\Big)\)。然后，因?yàn)?\(P(x_i)\) 和 \(Q(x_i)\) 是兩個(gè)多項(xiàng)式的結(jié)果，所以我們可以直接對(duì)每個(gè) \(P(x_i) \times Q(x_i) = Z(x_i)\)。對(duì)于 \(\Big(x_1, Z(x_1)\Big),\cdots,\Big(x_l, Z(x_l)\Big)\)，我們將點(diǎn)值表示法轉(zhuǎn)化回系數(shù)表示法，就能得到 \(P \times Q\) 的值。

整合思路，我們需要將系數(shù)表示法轉(zhuǎn)化為點(diǎn)值表示法，再將點(diǎn)值表示法轉(zhuǎn)化回系數(shù)表示法。

第一步被稱為 \(\mathbf{FFT}\)，第二部被稱為 \(\mathbf{IFFT}\)。

\(\mathbf{Part. 1 \ \ FFT}\)

\(\mathbf{FFT}\) 是為了解決如何快速將一個(gè)多項(xiàng)式從系數(shù)表示法轉(zhuǎn)化為多項(xiàng)式表示法的。如果我們直接暴力計(jì)算，我們要對(duì)于 \(n\) 個(gè)數(shù)，每個(gè)數(shù)計(jì)算 \(f(x)\)，總復(fù)雜度 \(\mathcal{O}(n^2)\)。（相關(guān)章節(jié)：\(\mathbf{Preview}，多項(xiàng)式表示法\)）

設(shè)我們現(xiàn)在想把 \(A(x) = \sum\limits_{i = 0}^{n - 1} a_i\times x^i\) 轉(zhuǎn)化為點(diǎn)值表示法。

在 \(\mathbf{Preview}\) 中的 多項(xiàng)式表示法 中，由 <1>，我們知道一個(gè)多項(xiàng)式可以被 \(n\) 個(gè)點(diǎn)唯一確定。

假設(shè)最終的點(diǎn)值表示法是 \(\Big(x_1, f(x_1)\Big),\cdots,\Big(x_n, f(x_n)\Big)\)，我們考慮將 \(x_1, \cdots, x_n\) 設(shè)為 \(w_n^0, \cdots, w_n^{n - 1}\)，然后計(jì)算 \(f(w_n^0),\cdots,f(w_n^{n - 1})\)。所以我們只需要計(jì)算 \(A(w_n^0),\cdots,A(w_n^{n - 1})\)。²

考慮分治計(jì)算這個(gè)值。我們把 \(A(x)\) 按照下標(biāo)奇偶性進(jìn)行分類：

然后繼續(xù)考慮構(gòu)造 \(A_1, A_2\)：

那么綜合 \((2)(3)\)：

由 <2> 知，我們需要把 \(w_n^k\) 代入多項(xiàng)式。

由于我們需要分治，考慮將 \(k\) 按照 \(k < \dfrac{n}{2}\) 和 \(k \geq \dfrac{n}{2}\) 考慮。

對(duì)于 \(k < \dfrac{n}{2}\)：（接下來的化簡如果不懂，可以嘗試結(jié)合 \(\mathbf{Preview}\) 中的 單位根 來看）

對(duì)于 \(k\geq \dfrac{n}{2}\)，考慮 \(k = k' + \dfrac{n}{2}\)：

我們發(fā)現(xiàn)，對(duì)于 \((5)\) 和 \((6)\) 的結(jié)果式，它們?cè)?\(A_1\) 和 \(A_2\) 多項(xiàng)式中代入得值是一樣的（都是 \(w_{\frac{n}{2}}^k\)，其中 \(k < \frac{n}{2}\)）。因此，如果我們分治求出來了 \(A_1(w_{\frac{n}{2}}^{k})\) 和 \(A_2(w_{\frac{n}{2}}^k)\)，我們就可以通過 \((5)(6)\) 來算出來 \(k < \dfrac{n}{2}, A(w_n^k)\) 和 \(k \geq \dfrac{n}{2},A(w_n^{k})\)，因此拼起來就是完整的 \(A(w_n^k)\)。

因此，我們只需要分治求出來 \(A_1(w_{\frac{n}{2}}^{k})\) 和 \(A_2(w_{\frac{n}{2}}^k)\)，然后求出來 \(A(w_n^k)\)，我們就可以得出 \(A\) 的點(diǎn)值表示法。對(duì)于每一層，我們只需要 \(\mathcal{O}(n)\) 的時(shí)間復(fù)雜度計(jì)算，總共 \(\mathcal{O}(\log n)\) 層，因此時(shí)間復(fù)雜度為 \(\mathcal{O}(n\log n)\)。

\(\mathbf{Part. 2 \ \ IFFT}\)

\(\mathbf{IFFT}\) 是為了解決如何快速將一個(gè)多項(xiàng)式從點(diǎn)值表示法轉(zhuǎn)化為系數(shù)表示法的。（相關(guān)章節(jié)：\(\mathbf{Preview}，多項(xiàng)式表示法\)）

假設(shè)我們對(duì)于多項(xiàng)式 \(A(x) = \sum\limits_{i = 0}^{n - 1} a_i \times x^i\)，求出來了 \(A\) 的點(diǎn)值表示 \(\Big(w_n^0, t_0\Big), \cdots, \Big(w_n^{n - 1}, t_{n - 1}\Big)\)，則我們想要通過 \(t\) 數(shù)組來還原出 \(a\) 數(shù)組。

我們考慮構(gòu)造數(shù)組 \(c\)，使得 \(c_k = \sum\limits_{i = 0}^{n - 1} t_i \times(w_n^{-k})^i\)。這個(gè)式子的含義是，我們考慮對(duì)于 \(f(x) = \sum\limits_{i = 0}^{n - 1}t_i \times x ^ i\) 這個(gè)多項(xiàng)式，代入 \((w_n^0, \cdots, w_n^{-(n - 1)})\) 計(jì)算 \(f(x)\)（也就是 \(t\) 數(shù)組）的點(diǎn)值表示法，得到 \(c_0, \cdots, c_{n - 1}\)。³

這里你可以這樣理解：我們?cè)趯?duì) \(A\) 求出代入 \((w_n^0, \cdots, w_n^{n - 1})\) 時(shí)的點(diǎn)值表示時(shí)，再對(duì)這個(gè)結(jié)果代入 \((w_n^0, \cdots, w_n^{-(n - 1)})\) 時(shí)求出點(diǎn)值表示，最后得到 \(c\) 數(shù)組。

考慮對(duì)這個(gè) \(c\) 數(shù)組進(jìn)行變換：

我們考慮 \(\sum\limits_{i = 0}^{n - 1}(w_n^{j - k})^i\) 如何快速計(jì)算。容易發(fā)現(xiàn)這是一個(gè)等比數(shù)列的形式，則：

• \(j - k = 0\)，則 \(\sum\limits_{i = 0}^{n - 1}(w_n^{j - k})^i = \sum\limits_{i = 0}^{n - 1}1^i = n\)。
• \(j = k \neq 0\)，則由于等比數(shù)列的比為 \(w_{n}^{j - k}\)，則 \(\sum\limits_{i = 0}^{n - 1}(w_n^{j - k})^i = \dfrac{(w_n^{j - k})^n - (w_n^{j - k})^0}{w_{n}^{j - k} - 1} = 0\)。

因此，我們發(fā)現(xiàn)，只有當(dāng) \(j = k\) 時(shí)，\(\sum\limits_{i = 0}^{n - 1}(w_n^{j - k})^i\) 為 \(n\)，其余情況均為 \(0\)。因此，\((21)\) 結(jié)果式轉(zhuǎn)化為：

因此，\(a_k = c_k \times \dfrac{1}{n}\)，而 \(a_k\) 就是我們想求的值！

考慮 \(c_k\) 是什么，由 <3>，我們知道 \(c_k\) 是對(duì)于 \(f(x) = \sum\limits_{i = 0}^{n - 1}t_i \times x ^ i\) 這個(gè)多項(xiàng)式，代入 \((w_n^0, \cdots, w_n^{-(n - 1)})\) 計(jì)算 \(f(x)\)（也就是 \(t\) 數(shù)組）的點(diǎn)值表示法。因此，我們只需要對(duì) \(t_0, \cdots, t_{n - 1}\) 求出來點(diǎn)值表示即可，這個(gè)和上面 \(\mathbf{Part. 1 \ \ FFT}\) 唯一的不同就是代入值中單位根的次數(shù)一個(gè)為正，一個(gè)為負(fù)。

所以，\(\mathbf{IFFT}\) 實(shí)際上就是對(duì) \(t\) 數(shù)組再做一遍 \(\mathbf{FFT}\)，然后對(duì)于每個(gè) \(c_k\) 乘上 \(\dfrac{1}{n}\) 就是 \(a_k\)。

\(\mathbf{Part. +\infin \ \ Details}\)

/*******************************
| Author:  DE_aemmprty
| Problem: P3803 【模板】多項(xiàng)式乘法（FFT）
| Contest: Luogu
| URL:     https://www.luogu.com.cn/problem/P3803
| When:    2025-07-26 15:03:20
| 
| Memory:  500 MB
| Time:    2000 ms
*******************************/
#include <bits/stdc++.h>
using namespace std;

int read() {
    char c = getchar(); int x = 0;
    while ((c < '0' || c > '9') && c != '-') c = getchar();
    while (c >= '0' && c <= '9') x = (x << 1) + (x << 3) + (c ^ 48), c = getchar();
    return x;
}

const int N = 3e6 + 107;
const long double pi = acos(-1);

int n, m, id[N], l;

struct complexor {
    double x, y;
    complexor (double p = 0, double q = 0) : x(p), y(q) {}
    complexor operator + (const complexor &t) const { return complexor(x + t.x, y + t.y); }
    complexor operator - (const complexor &t) const { return complexor(x - t.x, y - t.y); }
    complexor operator * (const complexor &t) const {
        return complexor(x * t.x - y * t.y, x * t.y + y * t.x);
    }
} p[N];

complexor omega(int n, int k) { return complexor(cos(pi * 2.0 * k / n), sin(pi * 2.0 * k / n)); }

void FFT(complexor *a, int op) {
    for (int i = 0; i < l; i ++)
        if (i < id[i]) swap(a[i], a[id[i]]);
    for (int d = 1; d < l; d <<= 1) {
        complexor w = omega((d << 1), op), W = 1;
        for (int k = 0; k < d; k ++) {
            for (int i = 0; i < l; i += (d << 1)) {
                complexor at = a[i + k], bt = W * a[i + d + k];
                a[i + k] = at + bt;
                a[i + d + k] = at - bt;
            }
            W = W * w;
        }
    }
}

void solve() {
    n = read(), m = read();
    for (int i = 0; i <= n; i ++) p[i].x = read();
    for (int i = 0; i <= m; i ++) p[i].y = read();
    l = 1; while (l <= n + m) l <<= 1;
    for (int i = 0; i < l; i ++)
        id[i] = (id[i >> 1] >> 1) | ((i & 1) * (l >> 1));
    FFT(p, 1);
    for (int i = 0; i < l; i ++)
        p[i] = p[i] * p[i];
    FFT(p, -1);
    for (int i = 0; i < n + m + 1; i ++)
        cout << (int) (p[i].y / l / 2.0 + 0.5) << ' ';
    cout << '\n';
}

signed main() {
    int t = 1;
    // t = read();
    while (t --) solve();
    return 0;
}

\(\mathbf{Question. 1}\)

第 \(42, 43\) 行的 swap 是什么意思？（為什么不是遞歸寫法？）

在 \(\mathbf{Part.1 \ \ FFT}\) 中，我們對(duì)每個(gè)多項(xiàng)式，按照奇偶分治。但是，我們?cè)?\(\mathbf{FFT}\) 的過程中，如果遞歸的去做，我們還要在計(jì)算的過程中將偶數(shù)項(xiàng)排在前面，奇數(shù)項(xiàng)排在后面，這樣的常數(shù)我們是不能接受的。那能不能快速的找到一種排序方式，直接把最終的順序找出來，這樣我能不用一邊遞歸一邊排序，而是一開始就排好序？

觀察結(jié)構(gòu)，你發(fā)現(xiàn)題目對(duì)于每個(gè) \(i\)，首先按照二進(jìn)制第一位排序，其次按照二進(jìn)制第二位排序……實(shí)際上，\(\mathbf{FFT}\) 的過程是在對(duì)每個(gè) \(i\)，它的二進(jìn)制從低位到高位進(jìn)行排序，也就是按照二進(jìn)制的翻轉(zhuǎn)串排序。（注意，這里的翻轉(zhuǎn)指第 \(1\) 位翻轉(zhuǎn)到第 \(n\) 位，而不是 \(0\to1,1\to0\)）

所以第 \(i\) 個(gè)數(shù)的排名其實(shí)就是 \(i\) 的二進(jìn)制翻轉(zhuǎn)串的值。（如假設(shè)總長 \(l = 8\)，\(i = 3 = (011)_2\)，那么 \(i\) 的翻轉(zhuǎn)串就是 \((011)_2 \to (110)_2\)。又由于最終序列按照翻轉(zhuǎn)串來排序，所以 \(i\) 的排名就是 \((110)_2 = 6\)）

那如何 \(\mathcal{O}(n)\) 求出來第 \(i\) 個(gè)數(shù)的翻轉(zhuǎn)串的值用于求排名？

我們考慮遞推。設(shè) \(f_i\) 表示第 \(i\) 個(gè)數(shù)的翻轉(zhuǎn)串的值，則我們考慮 比較 \(i\) 與 \(i' = i \gg 1\) 的關(guān)系。假設(shè) \(i = (011)_2,i' = (001)_2\)，那我們考慮兩個(gè)數(shù)的翻轉(zhuǎn)串分別為 \((110)_2, (100)_2\)。容易發(fā)現(xiàn)，由于 \(i\) 是 \(i’\) 左移一位加上 \((i \,\&\, 1)\)，所以 \(i\) 的翻轉(zhuǎn)串是 \(i'\) 右移一位加上 \((i\,\&\,1)\) 乘上最高位的值。因此，\(f_x = (f_{x \gg 1} \gg 1) \, \big| \, \Big((x \, \& \, 1) \times mx\Big)\)，其中 \(mx\) 為最高位。

\(\mathbf{Question. 2}\)

為什么 swap 之后，\(\mathbf{FFT}\) 求出來的值順序不會(huì)亂呢？

考慮回顧 \(\mathbf{Part.1 \ \ FFT}\) 的內(nèi)容。我們對(duì)于奇偶的下標(biāo)，分別求出了 \(A_1(w_{\frac{n}{2}}^{i})\) 和 \(A_2(w_{\frac{n}{2}}^i)\) 的值，然后我們按順序求出了 \(A(w_n^i)\) 的值并繼續(xù)往上遞歸。我們這里要注意不能混淆：我們確實(shí)打亂了 \(A\) 多項(xiàng)式的系數(shù)表示的順序，但是我們求出來的是點(diǎn)值表示，這個(gè)點(diǎn)值表示還是按照單位根的順序求出來的。所以 swap 之后 \(A\) 多項(xiàng)式存的點(diǎn)值表示是按順序的，沒有影響。