多項式乘法為什麼要繞一圈去頻域算？因為頻域裡乘法是 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 可行）。
哪裡用到？
- 大數乘法：n 位 × n 位，O(n log n)
- 字串匹配（卷積匹配）：模式中有通配符時，轉成多項式乘法
- 「差為 k 的點對數量」：兩個頻率陣列的卷積
- 圖像處理：高斯模糊、銳化等濾波操作底層是卷積，卷積用 FFT 加速
FFT 的精髓是：在時域做乘法很貴，去頻域後乘法免費——轉換的代價 O(n log n) 比直接算 O(n²) 更值得付。