Open xehoth opened 7 years ago
https://blog.xehoth.cc/FastFourierTransform/
两个n次多项式相加最直接的方法所需时间为O(n)，但是相乘最直接的方法所需时间为O(n2)。 快速傅里叶变换（Fast Fourier Transform，FFT）是一种可在 O(n log n)时间内完成的离散傅里叶变换（Discrete Fourier transform，DFT）算法，在 OI 中的主要应用之一是加速多项式乘法的计算。
https://blog.xehoth.cc/FastFourierTransform/
两个n次多项式相加最直接的方法所需时间为O(n)，但是相乘最直接的方法所需时间为O(n2)。 快速傅里叶变换（Fast Fourier Transform，FFT）是一种可在 O(n log n)时间内完成的离散傅里叶变换（Discrete Fourier transform，DFT）算法，在 OI 中的主要应用之一是加速多项式乘法的计算。