快速傅里叶变换（FFT，复数域）：在复数单位根上进行分治求和，实现多项式卷积/大整数乘法等，典型复杂度 O(n log n)。通过比特反转重排与蝶形操作，支持正/逆变换。
Description: Iterative Cooley–Tukey FFT over complex numbers with bit-reversal permutation; supports convolution by forward-transform, pointwise multiply, and inverse-transform with 1/n scaling. Time: O(n log n) Status: tested
-
函数/接口（据实现）
- void fft(vector<complex
>& a, bool invert) - a 长度为 2 的幂；invert=false 做正变换，true 做逆变换（并在末尾对每项除以 n）。
- template
vector convolution(const vector & A, const vector & B) - 返回实数近似的卷积结果；整数卷积可对结果四舍五入。
- vector
convolution_ll(const vector & A, const vector & B) - 采用“打包技巧”或两次 FFT，返回精确整数卷积（对浮点误差有防护）。
- void fft(vector<complex
-
核心思路（Cooley–Tukey，迭代版）
- 单位根：设 n=2^k，原根 w_n = e^{2πi/n}，各层使用 w_n 的幂。
- 比特反转：先按下标的二进制反转顺序重排 a，保证后续蝶形就地计算。
- 蝶形层：长度 len 从 2 递增至 n，步长为 len：
- 预计算每层的根步长 wn = e^{±2πi/len}（逆变换取共轭）。
- 对每个块 j..j+len-1，遍历前半段 i=j..j+len/2-1：
- u=a[i]，v=a[i+len/2]w；a[i]=u+v；a[i+len/2]=u−v；w=wn。
- 逆变换：同样的流程，但使用共轭根，并在末尾每项除以 n。
-
卷积（多项式/序列）
- 令 n 为 A、B 长度之和减 1 的最小 2 次幂。
- 填充零至长度 n，对两序列做 FFT；逐点相乘；做逆 FFT；四舍五入得到系数。
- 整数卷积的稳定方案：
- 双 FFT：将 A、B 拆成高/低位（如 1e4 基数），分别卷积后合成；
- 或单 FFT 打包：把 A 放实部，B 放虚部，经过一次 FFT 与复数乘法后拆解（实现需小心误差）。
-
复杂度
- FFT/逆变换 O(n log n)；卷积整体 2 次正变换 + 1 次逆变换 + O(n) 点乘。
-
数值与实现注意
- 长度需扩展到 2 的幂；极短长度可用 O(n^2) 朴素法更快。
- 精度：double 通常足够；规模大或系数大时可用 long double/分块基数降低误差。
- 预计算单位根可减少常数；不同 len 层不要重复调用三角函数。
- 结果四舍五入前应加微小偏移（如 0.5 的符号安全处理）以缓解浮点误差。
- 模域下的精确卷积优先用 099-数值算法-模域FFT / 109-数值算法-数论变换。
-
应用
- 多项式乘法、相关/卷积、循环卷积（需处理环状/补零）、大整数乘法。
- 变体：实序列 FFT（利用共轭对称性减半运算）、二维 FFT（对行列各做一次）。