第 6 章 · 02 多项式难点精讲 FFT/NTT/FWT ★

第 6 章 · 02 多项式难点精讲 FFT/NTT/FWT ★

本节定位：对应 OI Wiki docs/math/poly/（共 16 篇，重点是 fft.md、ntt.md、fwt.md）。难度：高阶（省选/IOI）。前置依赖：第 6 章 · 01 节数论（原根、模运算）、复数基础（docs/math/complex.md）。本节是难点精讲节（★），对 FFT 的蝶形运算、NTT 的原根替换、FWT 的位运算卷积做 Wiki 之外的慢节奏讲解，作 docs/math/poly/fft.md 的配套讲义，不重写 Wiki。

⚠️ 注意：这是数学章节的顶峰。Wiki 的 fft.md 写得详尽但节奏快，本节的任务是把"为什么这样算"拆开讲。学完本节建立直觉后，务必回 Wiki 看完整证明和代码。

为什么难

多项式这一节集中了三个高门槛：

1. 复数域与单位根：FFT 用复数 ω = e^(2πi/n)，需要复数运算和欧拉公式的直觉。
2. 蝶形运算分治：Cooley-Tukey 算法把多项式按奇偶分治，合并时"蝶形"结构抽象，位逆序置换极易写错。
3. 数论变换 NTT：用原根替换单位根，模数选取（998244353）有讲究，理解需要原根知识。

此外还有 FWT（位运算卷积）和一整套多项式高级运算（求逆/开方/ln/exp/牛顿迭代）。本节重点讲 FFT 蝶形，NTT 和 FWT 讲思路差异，高级运算只点名。

慢节奏精讲

一、FFT（docs/math/poly/fft.md）

问题：两个 n 次多项式相乘，朴素 O(n²)。FFT 把它降到 O(n log n)。

核心思想 1：系数表示 ↔ 点值表示

多项式有两种表示：

• 系数表示：A(x) = a0 + a1·x + ... + an·x^n，存系数数组。
• 点值表示：取 n+1 个不同的 x，存 (x, A(x)) 对。

关键：点值表示下，乘法是 O(n)——只要 A、B 取相同点，C = A·B 在这些点上的值就是对应相乘。朴素求值/插值都是 O(n²)，瓶颈在"求值"和"插值"。

核心思想 2：用单位根加速求值

如果能取"特殊点"让求值变快就好了。FFT 取 n 次单位根 ω_n^k = e^(2πik/n)（k = 0..n-1）。

单位根的三个性质（蝶形分治的基石）：

• 周期性：ω_n^n = 1。
• 对称性：ω_n^(k + n/2) = -ω_n^k。
• 折半定理：ω_n^(2k) = ω_(n/2)^k（把 n 个单位根的偶数幂恰好是 n/2 次单位根）。

利用折半定理，把 A(x) 按系数下标奇偶拆成 A0(x²)（偶次）和 A1(x²)（奇次）：

A(ω_n^k)       = A0(ω_n^(2k))  + ω_n^k · A1(ω_n^(2k))
                = A0(ω_(n/2)^k) + ω_n^k · A1(ω_(n/2)^k)
​

于是 n 个点的求值 → 两个 n/2 个点的子问题，分治！每层 O(n)，共 O(log n) 层，总计 O(n log n)。

★★★ 蝶形运算与位逆序置换

分治到单元素再合并，合并时同一层成对处理，像蝴蝶的翅膀，叫蝶形运算。Cooley-Tukey 算法用迭代（而非递归）实现：

1. 位逆序置换 bit-reversal：先把系数按"下标二进制位反转"重排，使递归的叶子顺序变成连续。
2. 逐层合并：从长度 2 的蝶形开始，倍增到长度 n，每层用单位根成对合并。

⚠️ 注意：位逆序置换是 FFT 代码里最容易写错的地方。n=8 时，下标 1（001）要换到位置 4（100）。建议先写一个独立的 rev[i] 预处理函数，单独调试通过再并入主流程。

逆变换 IDFT 只需把单位根换成 ω_n^(-k)，最后除以 n。

二、NTT（docs/math/poly/ntt.md）—— 数论变换

FFT 用复数有浮点误差，且不能直接对大整数取模。NTT 用原根替换单位根，把整个计算搬到模意义下。

• 模数 998244353 = 119 × 2²³ + 1（NTT 模数），它的原根 g = 3。
• g^((p-1)/n) mod p 满足单位根的三条性质（周期/对称/折半），所以 NTT 的算法结构和 FFT 完全一样，只是把复数 ω 换成 g^((p-1)/n) mod p。
• 优点：全整数运算，无浮点误差，可取模；缺点：模数必须选 NTT 友好的（如 998244353），否则不能直接用。

💡 学习提示：理解了 FFT 的蝶形，NTT 就是"换个单位根"。重点记 998244353 这个数和它的原根 3，比赛里看到"模 998244353"基本就是要 NTT。

三、FWT（docs/math/poly/fwt.md）—— 快速沃尔什变换

FWT 解决位运算卷积：c_k = Σ_{i op j = k} a_i b_j，op 是按位或/与/异或。

• 结构和 FFT 类似（正变换 → 点乘 → 逆变换），但变换核不是单位根，而是按位运算定义的矩阵。
• 三种卷积：或卷积（子集求和）、与卷积（超集求和）、异或卷积。
• 典型应用：SOS DP（子集和）、高维前缀和。

四、多项式高级运算（点名，深入回 Wiki）

docs/math/poly/ 还有一整套基于 NTT 的高级运算，都依赖牛顿迭代法（docs/math/poly/newton.md）：

• 求逆（docs/math/poly/inv.md）：已知 A 求 B 使 A·B ≡ 1。
• 开方、对数 ln、指数 exp（docs/math/poly/sqrt.md 等）。
• 多项式除法/取模（docs/math/poly/comp-rev.md）。

这些是省选/IOI 的"工具箱"，本节只点名，深入请逐篇读 Wiki。

常见误区

1. FFT 没补零到 2 的幂：蝶形分治要求长度是 2 的幂，乘积长度不是 2 的幂时要补零到最近的 2 的幂，否则位逆序和分治都会越界。
2. 位逆序写错：最常见 bug。务必单独预处理 rev 数组并验证。
3. NTT 模数选错：NTT 要求模数 p = k·2^m + 1 形式，998244353 是标准选择。题目给 1e9+7 时不能直接 NTT，要用 MTT（任意模数）。
4. 混淆 FFT 和 NTT 的单位根来源：FFT 用复数 e^(2πi/n)，NTT 用原根幂 g^((p-1)/n)，别在 NTT 代码里写复数。

练习建议

• P3803 【模板】多项式乘法（FFT）：先过这个，确认位逆序和蝶形无 bug。
• P3803 的 NTT 版本（P1919 A*B Problem 升级版）：体验无浮点误差的整数卷积。
• 进阶：多项式求逆（P4238）、牛顿迭代（P4725 多项式对数函数）。
• 学法：FFT 模板题务必手写一遍（不抄模板），位逆序和蝶形写对一次，后面 NTT/FWT 就是套用。

💡 学习提示：FFT 的"理解"和"写对代码"差距很大。建议先用 n=8 手算一遍位逆序和蝶形，再写代码，最后用模板题验证。手算这一步省不掉。

本节要点

• FFT 用单位根 + 奇偶分治，把多项式乘法从 O(n²) 降到 O(n log n)。
• 蝶形运算 + 位逆序置换是 FFT 的实现核心，也是最容易写错的地方。
• NTT 用原根替换单位根（模数 998244353，原根 3），结构与 FFT 相同，避免浮点误差。
• FWT 解决或/与/异或的位运算卷积。
• 多项式求逆/开方/ln/exp/牛顿迭代是省选工具箱，深入见 docs/math/poly/ 各页。