FFT,NTT学习总结

快速傅里叶变换（FFT）是一种高效计算离散傅里叶变换（DFT）或其逆变换的方法，极大地简化了计算复杂度。它广泛应用于工程、科学和数学领域。FFT的基本原理是将DFT矩阵分解为稀疏因子之积，从而将复杂度从O(n^2)降低至O(n log n)。多项式乘法是FFT的一个典型应用。虚者计算两个多项式(A(x) = a_0 + a_1x + a_2x^2 + ... + a_{n-1}x^{n-1})和(B(x) = b_0 + b_1x + b_2x^2 + ... + b_{n-1}x^{n-1})的乘积(C(x) = A(x)B(x))。最直接的方法是枚举次数，计算系数和，但这需要O(n^2)的时间复杂度。通过FFT，将多项式从系数表示转换为点值表示，乘法变为线性操作，复杂度降至O(n log n)。多项式表示有系数表示和点值表示两种。系数表示法通过多项式各项次数的系数表示多项式，点值表示法通过多项式碰穗在某些点的值来表示多项式。点值表示法下，多项式乘法变得直接，但直接计算点值的复杂度仍然是O(n^2)。利用复数和单位根，FFT实现系数表示到点值表示的快速转换，进而实现多项式乘法的高效计算。FFT的核心思想是分治。将多项式的系数表示转换为点值表示时，通过分治奇偶项，利用单位根的性质进行计算。这使得计算复杂度降低至O(n log n)。得到点值表示后，多项式乘法变为简单相乘。然后，使用快速傅里叶逆变换（IDFT）将结果的点值表示转换回系数表示。实现FFT有递归和非递归两种方式。递归版FFT相对直观，但常数较大；非递归版（蝴蝶变换）通过预处理实现快速转换，常数较小。快速数论变换（NTT）是FFT的整数域版本，适用于模数为质数的情况。NTT将多项式乘法限制在有限域内，适用于生成函数、高精度乘法和分治NTT等特定问笑誉卜题。原根和模数的选择是NTT的关键。通过FFT和NTT，可以高效解决多项式乘法、生成函数、高精度乘法和分治NTT等数学问题。在实际应用中，选择合适的FFT或NTT实现方式和参数可以显著提高算法的性能。