OI 题解索引与随笔文章

知识演进图谱

前置基础核心概念算法实现应用场景

拖拽节点 · 滚轮缩放 · 点击高亮

0核心准备：绘制技能树

「向上爬」的梯子

FFT 是由以下基础零件组装而成的。点击图谱中的节点可查看依赖关系：

🔢复数与复平面

📐欧拉公式

📈多项式表示法

🧩分治思想

🌀单位根

💻位运算基础

大白话通关自测

复数：能否一句话说清 $a+bi$ 的几何意义？能否解释为什么复数乘法就是「模长相乘、辐角相加」？
欧拉公式：能否解释 $e^{i\theta}=\cos\theta+i\sin\theta$，并说明为什么 $e^{i\pi}+1=0$？
多项式：能否说清「系数表示法」和「点值表示法」的区别？为什么 $n$ 个点能唯一确定一个 $n-1$ 次多项式？
分治：能否用白话讲清归并排序为什么是 $O(n\log n)$？能否解释分治三要素（分解、解决、合并）？
单位根：能否在复平面上画出 $n$ 次单位根？为什么它们「成对出现、互为相反数」？

1认个脸熟 — 灵魂三问

① 它叫什么，在生活里长啥样？

快速傅里叶变换（Fast Fourier Transform, FFT）本质上是高效计算多项式乘法和离散傅里叶变换的算法。

生活类比：合唱团分声部。想象你要把两个大合唱团的歌声「乘」在一起——如果让每位歌手两两对唱（$O(n^2)$），排练厅得炸。聪明的指挥家把合唱团按奇偶拆成两个低声部和高声部，分别排练好后再合成，工作量骤降到 $O(n\log n)$。

② 它能帮我们解决什么「挨饿」问题？

如果没有 FFT，两个 $n$ 次多项式相乘需要 $O(n^2)$ 时间（逐项相乘）：

C(x)=A(x)\cdot B(x),\quad C_k=\sum_{i=0}^{k}A_iB_{k-i}

当 $n=10^5$ 时，$n^2=10^{10}$，直接计算会超时。FFT 将复杂度降到 $O(n\log n)$，约 $1.7\times 10^6$ 量级，快了近 6000 倍。

③ 它的终极局限是什么？

长度限制：标准 FFT 要求长度是 2 的幂，非 2 次幂需要补零到最近的 2 次幂。
浮点精度：涉及复数浮点运算，当数值很大时可能产生精度误差（此时需要 NTT / 快速数论变换）。
不适用于稀疏多项式：若多项式只有少数非零项，直接逐项乘反而更快。

2纸上谈兵 — 人肉模拟

微缩模型：$A(x)=1+2x+3x^2+4x^3$ 与 $B(x)=5+6x+7x^2+8x^3$

目标：计算 $C(x)=A(x)\cdot B(x)$。

人肉模拟蝴蝶变换（$n=4$，单位根 $\omega_4=e^{-2\pi i/4}=-i$）

第一步：位逆序置换。将系数按二进制位反转重排：

\begin{aligned} A &: [1,2,3,4] \xrightarrow{\text{bit-reverse}} [1,3,2,4] \\[4pt] B &: [5,6,7,8] \xrightarrow{\text{bit-reverse}} [5,7,6,8] \end{aligned}

第二步：蝴蝶操作（层数 $k=1$，间距 $d=2$）。

对于 $A$，处理对 $(1,3)$ 和 $(2,4)$：

\begin{aligned} A[0]' &= A[0] + \omega_4^0 \cdot A[1] = 1 + 1 \cdot 3 = 4 \\ A[1]' &= A[0] - \omega_4^0 \cdot A[1] = 1 - 1 \cdot 3 = -2 \\ A[2]' &= A[2] + \omega_4^0 \cdot A[3] = 2 + 1 \cdot 4 = 6 \\ A[3]' &= A[2] - \omega_4^0 \cdot A[3] = 2 - 1 \cdot 4 = -2 \end{aligned}

第三步：得到 DFT 结果。将两个 DFT 结果逐点相乘后再做 IDFT（逆变换），除以 $n$ 即得最终系数：

$$C(x)=5+16x+34x^2+60x^3+61x^4+52x^5+32x^6$$

蝴蝶操作可视化（$n=8$ 标准信号流向图）

下图直观展示了迭代 FFT 中数据的流动方向。输入系数经过位逆序重排后，在每一层按跨度逐渐增大的方式交叉合并（蝴蝶操作），最终在右侧输出自然序的 DFT 结果：

抓住「偷懒的瞬间」

          关键洞察：蝴蝶操作利用单位根的对称性（$\omega_n^{k+n/2}=-\omega_n^k$），每一层只需计算一半的乘法——$n$ 个元素参与但只做 $n/2$ 次复数乘法。共 $\log_2 n$ 层，总复杂度 $O(n\log n)$。
        

3打造自动化厨具 — C++ 模板

最干净的代码骨架（迭代 FFT）

// --- 复数结构 ---
struct Complex {
    double real, imag;
    Complex(double r = 0, double i = 0) : real(r), imag(i) {}
    Complex operator+(const Complex& b) const { return {real + b.real, imag + b.imag}; }
    Complex operator-(const Complex& b) const { return {real - b.real, imag - b.imag}; }
    Complex operator*(const Complex& b) const {
        return {real * b.real - imag * b.imag, real * b.imag + imag * b.real};
    }
};

// --- 迭代 FFT (inverse=false: DFT, inverse=true: IDFT) ---
void fft(vector<Complex>& a, bool inverse) {
    int n = a.size();
    // 位逆序置换：把兄弟排在正确的位置上
    for (int i = 0, j = 0; i < n; ++i) {
        if (i > j) swap(a[i], a[j]);
        for (int k = n >> 1; (j ^= k) < k; k >>= 1);
    }
    // 蝴蝶操作：逐层合并
    for (int len = 2; len <= n; len <<= 1) {
        double ang = 2 * M_PI / len * (inverse ? -1 : 1);
        Complex wlen(cos(ang), sin(ang));    // 本层单位根
        for (int i = 0; i < n; i += len) {
            Complex w(1, 0);               // 旋转因子，随 j 倍增
            for (int j = 0; j < len / 2; ++j) {
                Complex u = a[i + j];                // 左兄弟
                Complex v = a[i + j + len/2] * w;  // 右兄弟 × ω
                a[i + j] = u + v;                    // 合并上支
                a[i + j + len/2] = u - v;          // 合并下支
                w = w * wlen;                         // 旋转到下一对
            }
        }
    }
    if (inverse)
        for (auto& x : a) x.real /= n, x.imag /= n;  // IDFT 别忘了除以 n！
}

// --- 多项式乘法入口 ---
vector<long long> multiply(const vector<int>& A, const vector<int>& B) {
    int n = 1;
    while (n < A.size() + B.size() - 1) n <<= 1;  // 补到 2 的幂
    vector<Complex> a(n), b(n);
    for (int i = 0; i < A.size(); ++i) a[i] = Complex(A[i], 0);
    for (int i = 0; i < B.size(); ++i) b[i] = Complex(B[i], 0);
    fft(a, false); fft(b, false);
    for (int i = 0; i < n; ++i) a[i] = a[i] * b[i];   // 频域逐点乘
    fft(a, true);
    vector<long long> res(A.size() + B.size() - 1);
    for (int i = 0; i < res.size(); ++i) res[i] = llround(a[i].real);
    return res;
}

踩坑备忘录

⚠️ 常见低级错误：

数组大小：结果长度为 len(A)+len(B)-1，FFT 长度需 ≥ 此值且为 2 的幂。漏加 -1 导致 WA。
IDFT 未除 n：逆变换后忘记把实部和虚部都除以 n，输出数值比正确答案大 n 倍。
角度符号：DFT 用 $\omega_n=e^{-2\pi i/n}$（顺时针），IDFT 用 $\omega_n=e^{+2\pi i/n}$（逆时针），inverse 标志下的 ang 符号必须对调。
精度取整：用 llround 而非 (long long)(x+0.5)。C/C++ 中强制类型转换向零截断：$(long long)(-0.6+0.5)=(long long)(-0.1)=0$，而正确答案应为 $-1$（四舍五入）。llround 能正确执行远离零的舍入，避免负数 FFT 结果取整时的符号错误。
位逆序写错：内层循环 (j ^= k) < k 的优先级——先 ^= 再比较。

NTT 对照模板（快速数论变换 — 模 $998244353$，原根 $3$）

现代 OI 中纯浮点数 FFT 的考频正在下降。NTT 用模 $998244353$（$=119×2^{23}+1$）下的原根 $g=3$ 替代复数单位根，代码结构几乎完全一致：

维度	FFT	NTT
运算域	复数 $\mathbb{C}$	模 $p$ 的有限域 $\mathbb{F}_p$
单位根	$\omega_n=e^{-2\pi i/n}$	$g^{(p-1)/len}$（$g=3$ 为模 $998244353$ 的原根）
乘法	`Complex(ac-bd, ad+bc)`	`1LLab % MOD`
除 $n$	实部虚部分别除以 $n$	乘 $n$ 的逆元 $n^{-1}mod p$
精度	浮点误差，需 `llround`	完全精确（模意义下）
限制	任意长度	$n$ 必须是 $(p-1)$ 的因子（$p-1=2^{23}×119$）

const int MOD = 998244353, G = 3;
inline int qpow(int a, int b) { int r=1; for(;b;b>>=1,a=1LL*a*a%MOD) if(b&1) r=1LL*r*a%MOD; return r; }

void ntt(vector<int>& a, bool invert) {
    int n = a.size();
    // 位逆序置换 — 与 FFT 完全相同
    for (int i=1, j=0; i<n; i++) {
        int bit = n >> 1;
        for (; j&bit; bit >>= 1) j ^= bit;
        j ^= bit;
        if (i < j) swap(a[i], a[j]);
    }
    // 蝴蝶操作 — 只把 Complex 换成 int，乘法加上取模
    for (int len=2; len<=n; len<<=1) {
        int wlen = qpow(G, (MOD-1)/len);   // ← 单位根 → 原根
        if (invert) wlen = qpow(wlen, MOD-2); // 逆变换用逆元
        for (int i=0; i<n; i+=len) {
            int w = 1;
            for (int j=0; j<len/2; j++) {
                int u = a[i+j];
                int v = 1LL * a[i+j+len/2] * w % MOD;
                a[i+j]         = (u+v) % MOD;
                a[i+j+len/2]   = (u-v+MOD) % MOD;
                w = 1LL * w * wlen % MOD;
            }
        }
    }
    if (invert) { int inv_n = qpow(n, MOD-2); for (int &x:a) x=1LL*x*inv_n%MOD; }
}

进阶：极致卡常（预处理单位根 / 原根数组）

在 OI 竞赛中多项式题目的时限经常只有 1~2 秒。标准模板每次蝴蝶内层循环都做一次 w = 1LL * w * wlen % MOD（或 Complex w * wlen），log₂n 层 × n/2 次 = 大量重复乘法。预处理可减少约 30%~50% 的常数开销。

// NTT 常量优化：预处理所有层级的单位根（原根幂）
vector<int> roots;  // 全局数组，长度 = n

void precompute_roots(int n) {
    roots.resize(n);
    int wlen = qpow(G, (MOD-1)/n);
    roots[0] = 1;
    for (int i=1; i<n; i++)
        roots[i] = 1LL * roots[i-1] * wlen % MOD;
}

// 优化后的蝴蝶操作（以 NTT 为例）
for (int len=2; len<=n; len<<=1) {
    int half = len >> 1;
    int step = n / len;
    for (int i=0; i<n; i+=len) {
        for (int j=0; j<half; j++) {
            int w = roots[j * step];  // ← 查表替代逐次乘法
            int u = a[i+j];
            int v = 1LL * a[i+j+half] * w % MOD;
            a[i+j]       = (u+v) % MOD;
            a[i+j+half]  = (u-v+MOD) % MOD;
        }
    }
}

位逆序安全升级：预处理 rev 数组
现代 OI 选手更推荐用预处理 rev[] 的方法替代内联位逆序递推。优势：常数更小、多组数据时更安全、代码更短。

// 预处理 rev 数组（在 init 中调用一次）
int rev[MAXN], k;  // k = ceil(log2(n))
void init_rev(int n) {
    k = 0; while ((1 << k) < n) k++;
    for (int i=0; i<n; i++)
        rev[i] = (rev[i>>1] >> 1) | ((i&1) << (k-1));
}
// NTT 主函数开头直接：
for (int i=0; i<n; i++) if (i < rev[i]) swap(a[i], a[rev[i]]);

递推公式解释：rev[i] 的二进制 = 去掉 i 最低位后的反转左移一位，最后根据 i 最低位填最高位。预处理后每次 NTT 只做一次 O(n) 的 swap，比内联递推的位运算循环更简洁稳定。

关键思想：单位根序列 roots[k*step] 恰好是长度 len 时的第 k 个旋转因子。一次 O(n) 预处理 + O(1) 查表，省掉每层内循环的乘法递推。CF 上的多项式题几乎都要求此优化才能通过时限。

          模数小贴士：为什么 OI 都喜欢 998244353？

          $$998244353 = 119 \times 2^{23} + 1$$
          这个质数的精妙之处在于 $p-1 = 119 \times 2^{23}$ 中含有 $2^{23}$（约 838 万） 的因子。NTT 要求单位根的阶（即变换长度 $n$）必须整除 $p-1$，因此 998244353 能完美支持所有 $n \le 2^{23}$ 的 2 次幂长度变换。这也是为什么 Codeforces / 洛谷的多项式题几乎清一色指定这个看似「随机的」质数。

          其原根 $g=3$，在 NTT 中替代 FFT 的复数单位根：$\omega_n = g^{(p-1)/n}$，实现实数域到有限域的无缝迁移。

4试炼闯关 — 知识点演进计划（全部选自 Codeforces）

原创验证题：小鹏的物资调度

          题目背景：小鹏负责在 $n$ 个城市之间调度物资。第 $i$ 种物资从城市 A 出发有 $a_i$ 种运输路线，到达城市 B 有 $b_i$ 种接收方案（$0 \le i < n$）。将所有物资合并一次运输后，最终方案数向量 $c$ 满足 $c_k = \sum_{i+j=k} a_i \cdot b_j$（$0 \le k < 2n-1$）。
        

Subtask	分值	限制	策略
Subtask 1	20 pts	$n \le 1000$	直接提交 Tab 5 中的 $O(n^2)$ `brute_mul` 暴力代码即可通过。意图：分段拿分是比赛策略，先用暴力稳拿 20 分再攻正解。
Subtask 2	80 pts	$n, M \le 10^5$（答案多项式次数 $\le 2\times10^5$，NTT 长度取 $2^{18}=262144$ 即可）	暴力超时，必须使用 NTT（模 $998244353$）或 FFT 正解。数组开到 `MAXN = 1 << 18`，配合预处理单位根卡常。可配合「预处理单位根数组」的卡常优化确保时限通过。

第一关：纯模板题

CF 1096G Lucky Tickets （Rating 2400, Educational Round 57）

构造生成函数 $f(x)=\sum a_i x^i$（$a_i$ 表示数字 $i$ 是否可选），则 $n$ 位 Lucky Ticket 的方案数等于 $[f(x)]^{n/2}$ 各系数平方和。用 FFT/NTT + 多项式快速幂（倍增） 即可。本质就是多项式乘法的反复套用，不绕弯。

目标：一次 AC，确认位逆序、蝴蝶操作、IDFT 除 n、NTT 模数 998244353 均正确。

第二关：穿马甲的单点题

CF 528D Fuzzy Search （Rating 2500）

题目表面是字符串模糊匹配——允许模式串每位在文本串对应位置 ±$k$ 范围内匹配。字符集仅 4 种（A/T/C/G），对每种字符分别构造 0/1 数组，将模式串反转后做卷积，四种字符的匹配数之和等于 $m$ 则该位置成功。一眼看不出是 FFT，看到「反转 + 卷积」才恍然大悟。

第三关：联合作战 — 多考点融合

CF 438E The Child and Binary Tree （Rating 3100）

求权值在集合 $\{c_i\}$ 中的二叉树计数。设生成函数 $G(x)$ 和 $C(x)$，导出 $G=C\cdot G^2+1$，解得 $G=\frac{2}{1+\sqrt{1-4C}}$。需要 多项式开根 + 多项式求逆，FFT/NTT 作为底层卷积引擎贯穿始终。这道题让你真正把 FFT 当工具用，而非主角。

CF 755G PolandBall and Many Other Balls （Rating 3200）

$n$ 个球选 $m$ 组（每组 1 或 2 个相邻球）。DP 递推 $F_n=(x+1)F_{n-1}+xF_{n-2}$，可用矩阵快速幂 + NTT（$O(k\log k\log n)$），或解特征方程走多项式开根 + 快速幂路线（$O(k\log k)$）。

第四关：变式魔王题

CF 623E Transforming Sequence （Rating 3300）

DP + 倍增 + 卷积优化。模数是 $10^9+7$，NTT 的原根模数 998244353 不适用，必须用任意模数 NTT（MTT / 拆系数 FFT）。这是把通用 FFT 模板逼到墙角、迫使你掌握 MTT 的题。

CF 553E Kyoya and Train （Rating 3300）

期望 DP + Floyd 最短路 + 分治 FFT。图上有环 → 按时序分治消除后效性；转移是卷积 → 分治 FFT。$O(mT\log^2 T)$。这道题把 FFT、DP、图论、分治全部缝合在一起，是真正的变式魔王。

5归档入库 — 把技能挂上树

大白话闭眼复述

          3 分钟老奶奶讲解：

          快速傅里叶变换就是给多项式乘法开了个高速公路。直接乘要每个人两两见面，太慢。FFT 的妙招是：先把多项式「翻译」成频域里的点值（DFT），频域里乘法特别简单，就对应位置一乘就行；算完再「翻译」回来（IDFT）。翻译的过程用了分治——把队伍一拆二、二拆四，每次拆半都能省一半工，最后总共省到 $n\log n$。核心工具是复平面上的「旋转木马」——单位根，它们成对出现、方向相反，让合并时能复用一半结果。

寻找新邻居（FFT 之后可以挂靠的技能）

快速数论变换 NTT：用模意义下的原根替代复数单位根，避免浮点误差，是 FFT 的离散化兄弟。前置：数论原根、模运算。
快速沃尔什变换 FWT：将「逐位卷积」加速到 $O(n\log n)$，与 FFT 同属「变换加速卷积」家族。前置：位运算卷积、高维前缀和。
分治 FFT / CDQ 分治：FFT 加速分治过程中卷积计算，是 FFT 的高阶战术应用。
生成函数：FFT 是实现多项式操作的核心引擎，有了它才能高效操作生成函数进行组合计数。
Bluestein 算法 / Chirp Z-Transform：处理非 2 次幂长度或非等间距采样的 FFT 变体。

知识归档校验清单

能在 5 分钟内默写出迭代 FFT 完整模板
能对着代码逐行向老奶奶解释蝴蝶操作
能独立手算 $n=4$ 的 DFT 全过程（含位逆序和蝴蝶）
知道什么时候该用 NTT 而非 FFT（取模 / 精度敏感场景）
能说清 FFT、NTT、FWT 三者的异同和应用边界

对拍：暴力验证策略

          FFT 极易写错下标或位运算，对拍是必备安全网。写一个 $O(n^2)$ 的纯暴力多项式乘法，与 FFT/NTT 的输出做 Diff 对比。初期练习建议每改一次模板就随机生成小数据对拍一次。
        

// O(n²) 暴力多项式乘法 — 用于对拍验证
vector<long long> brute_mul(const vector<long long>& a, const vector<long long>& b) {
    int na = a.size(), nb = b.size();
    vector<long long> c(na + nb - 1);
    for (int i=0; i<na; i++)
        for (int j=0; j<nb; j++)
            c[i+j] += a[i] * b[j];
    return c;
}
// 对拍流程：生成随机小系数（|a_i| ≤ 100，n ≤ 50）
// → 分别跑 FFT 和 brute_mul → 逐位比较 → 不一致则输出反例

数据生成器示例：for(int i=0;i<n;i++) a[i]=rand()%200-100;（系数随机 ±100），用 diff 或脚本逐位比对 FFT 与暴力输出，确保万无一失后再提交 OJ。

快速傅里叶变换 FFT