FFT，即快速傅里叶变换（Fast Fourier Transform），是一种高效的算法，用于将信号从时域转换到频域。它通过减少计算量，将傅里叶变换的计算复杂度从O(N^2)降低到O(NlogN)，其中N是数据点的数量。FFT在信号处理、图像处理、通信等

FFT&NTT的小总结 前言 最近正在学 \(FFT\) ，然后一脸迷惑。 我看我是完全不懂……。 什么是 \(FFT\&NTT\) ？ 在讲 \(FFT\&NTT\) 之前，我觉得我有必要先介绍一下 \(DFT\&IDFT\) 。 \(DFT\&IDFT\) ： \(DFT\:(Discrete\:Fourier\:Transform)\) ：离散傅里叶变换。而 \(IDFT\) 自然就是离散傅里叶逆变换了。 离散傅里叶变换是傅里叶变换在时域和频域上都呈离散的形式，将信号的时域采样变换为其DTFT的频域采样。在形式上，变换两端（时域和频域上）的序列是有限长的，而实际上这两组序列都应当被认为是离散周期信号的主值序列。——百度百科 当然，作为一名 \(oier\) ，我们并不需要知道离散傅里叶变换有何重要的物理意义（除非你想转物理），我们只需要知道，这个变换能够帮助我们将一个多项式以另外一种形式表达。 让我们先考虑这样一个问题：假如有两个多项式，我们要去计算它们的乘积，只能去枚举一个多项式的每一个点，再和另外一个多项式的每一个点相乘，这样的时间复杂度是 \(O(n^2)\) 的。 太慢了……有没有更好的算法？ 自然是有的（不然我问这个问题干嘛？），我们都知道，\(n\) 个点能够唯一确定一个 \(n-1\) 次的多项式，那么我们对于多项式就有了一种新的表示方法：点值表示法。然后我们假装惊奇地发现：在点值表示法下，两个多项式相乘的时间复杂度居然是 \(O(n)\) 的，只需要枚举每个横坐标，将他们的纵坐标相乘就好了。那么我们就有了一个 \(O(n)\) 的算法。像这样朴素将系数转换成点值算法就叫 \(DFT\)，点值转系数叫 \(IDFT\)。 等等，明明已经能够在线性时间内算出结果，为什么还说是朴素算法？因为事实上，还有一个问题需要考虑，就是如何将一个多项式的系数表示变成点值表示。显而易见，随便带入 \(n\) 个点就可以了，但是这样转换的时间复杂度是 \(O(n^2)\) 的，果然很朴素。 如果我们能够快速地解决表示的转换，那么问题就迎刃而解了。这就需要用到 \(FFT\&NTT\) 。 \(FFT\&NTT\) ： 如果你十分耐心地看到了这里并且以为我将会非常详细地去讲解 \(FFT\&NTT\) ，那你就错了，哈哈哈哈不好笑。网上讲 \(FFT\) 的比较多，本蒟蒻就不再去插一脚了，就只是稍微地讲一讲什么是 \(FFT\&NTT\) （免得像我一样学了半天了还不知道这玩意儿是干嘛的），以及个人认为 \(FFT\) 中比较重要的一些东西。 这里推荐oi-wiki的官方教程和个人认为讲的比较好的几篇博客：十分简明易懂的FFT，FFT详解。 于心不忍，我还是稍微讲讲吧。 \(FFT\:(Fast\:Fourier\:Transform)\) ：快速傅里叶变换，是对离散傅里叶变换的优化。能够做到在 \(O(nlogn)\) 的时间复杂度内将一个多项式从点值表示法变成系数表示法。其算法原理是在复数平面内的单位圆上选取 \(2^n\) 个复数作为点的横坐标，代入多项式求得其纵坐标，（当时没学复数的时候一脸迷惑：这玩意儿还能带进去算？）。当然，这 \(2^n\) 个点可不是随便选的，这就要用到单位复数根的性质了： 周期性：\(\omega_N^{n+N}=\omega_N^n\) 对称性：\(\omega_N^{n+\frac{N}{2}}=-\omega_N^n\) 降次性：\(\omega_{kN}^{kn}=\omega_N^n\) \(NTT\:(Number\:Theoretic\:Transform)\) ：快速数论变换，是对 \(FFT\) 的一次改良。\(FFT\) 好是好，但是也是有一些缺点的，比如手写complex大量的 double 运算既会损失精度（世界上卡你精度的方法有千千万万种），又自带大常数。所以这个时候我们就只能用 \(NTT\) 了。 仔细思考一下，\(FFT\) 的本质是什么？是什么让 \(FFT\) 能够做到 \(O(nlogn)\) 的复杂度？其实就是我之前提到的关于单位根的那些性质。那有没有什么其他的东西也拥有单位根的这些性质呢？答案是有的，原根就具有和单位根一样的性质，建议自己证明一遍。 我们可以仿照单位复数根的形式，也将原根的取值看成一个圆，不过这个圆只有有限个点，每个点表达的是模数的剩余系中的值，可以证明其具有单位根的三个性质： 周期性：利用欧拉定理可得 \(r^k\) 会以 \(\varphi(p)\) 为一个循环节。