多項式乘法為什麼要繞一圈去頻域算？因為頻域裡乘法是 O(n)，轉換的代價比直接算還小。
問題：大數/多項式乘法的瓶頸
兩個 n 次多項式相乘，係數對係數直接算是 O(n²)。兩個 n 位大數相乘同理——高中乘法。
n = 10^6 時，O(n²) = 10^12，絕對超時。
FFT 的突破：換一種表示法，讓乘法變簡單。
兩種多項式表示法
係數表示：A(x) = a₀ + a₁x + a₂x² + ... + aₙxⁿ
→ 兩個 n 次多項式相乘，直接算需要 O(n²)
點值表示：用 n+1 個「(輸入, 輸出)」對唯一確定多項式
A 的點值 × B 的點值 = (A×B) 的點值
→ 逐點相乘，O(n)關鍵問題：怎麼在係數表示和點值表示之間快速轉換？
單位根讓轉換快起來
選 n 個特殊的輸入點——n 次單位根（ω, ω², ω³, …, ωⁿ = 1）：
ωₙ = e^(2πi/n) = cos(2π/n) + i×sin(2π/n)
特殊性質：ωₙ^(k+n/2) = -ωₙ^k （消去引理）有了這個性質，可以把 n 點 DFT 拆成兩個 n/2 點 DFT：
A(x) = A_even(x²) + x × A_odd(x²)
A[k] = A_even[k] + ω^k × A_odd[k] （蝴蝶操作）
A[k + n/2] = A_even[k] - ω^k × A_odd[k]每層 n 次操作，共 log n 層，總 O(n log n)。
完整流程
多項式乘法（A × B）：
1. FFT(A 的係數) → A 在 n 個單位根的點值
2. FFT(B 的係數) → B 在 n 個單位根的點值
3. 逐點相乘 → (A×B) 的點值，O(n)
4. IFFT（逆變換） → (A×B) 的係數
IFFT = FFT 的共軛版本 + 除以 n競程中的 NTT（數論變換）
FFT 用複數浮點運算，精度問題在競程中很麻煩（係數可能是整數，要求精確答案）。
NTT 用模質數的整數單位根，避免浮點——競程標準做法，模數通常選 998244353（= 119 × 2²³ + 1，保證 2²³ 次方的 NTT 可行）。
好消息是你幾乎不用重寫演算法。NTT 跟 FFT 的骨架一模一樣（一樣拆奇偶、一樣蝴蝶操作），只是把複數單位根 ω 換成模意義下的「原根」——998244353 的原根是 3：
long g = 3; // 998244353 的原根
long wn = modPow(g, (MOD - 1) / n, MOD); // 模意義下的 n 次主根，取代 e^(2πi/n)
// 蝴蝶操作、拆奇偶、log n 層，全部照 FFT 那套，只是乘法都改成模乘三種做法擺一起，取捨就清楚了：
| 方法 | 時間 | 精度 |
|---|---|---|
| 暴力多項式乘法 | O(n²) | 精確 |
| FFT | O(n log n) | 浮點誤差 |
| NTT | O(n log n) | 模意義下精確 |
要精確整數答案（競程判對錯）就用 NTT；資料本來就是浮點、或不在意末位誤差（信號、圖像）就用 FFT。
哪裡用到？
- 大數乘法：n 位 × n 位，O(n log n)
- 字串匹配（卷積匹配）：模式中有通配符時，轉成多項式乘法
- 「差為 k 的點對數量」：兩個頻率陣列的卷積
- 圖像處理：高斯模糊、銳化等濾波操作底層是卷積，卷積用 FFT 加速
🎬 互動視覺化：FFT 動畫 — 看係數表示怎麼被單位根「取樣」成點值、蝴蝶操作一層層合併，再 IFFT 轉回係數，繞頻域這一圈為什麼比直接乘還快，用動的比用想的清楚。
FFT 的精髓是：在時域做乘法很貴，去頻域後乘法免費——轉換的代價 O(n log n) 比直接算 O(n²) 更值得付。
接下來往哪走
- 2-SAT：O(n) 解布林可滿足性問題 — 下一篇：從數學變換切到邏輯問題的圖論解法
- Divide and Conquer 分治法 — FFT 的骨架就是分治：拆半、遞迴、蝴蝶操作合併
- Math Algorithms 數學演算法 — NTT 用到的模運算、快速冪基礎在這裡