畜中牲都不一定能理解的 FFT 未完成

前言

借鉴

看了一上午的 FFT 竟然学会了。于是写下这篇来纪念。

期间涉及复平面的相关知识，我这个畜中牲竟然懂了，真是神奇，请不要望而却步，勇于面对，死磕一下总是好的。

FFT 中文名 快速傅里叶变换

OI 经常拿它来解决高精度乘法的问题。朴素高精乘是 \(O(n ^ 2)\) 的，而用 FFT 是 \(O(n\log n)\) 的，可以解决两个 \(10^{1000000}\) 级别的数乘起来的问题。

What is FFT

快速傅里叶变换（FFT）是一种能在 \(O(n\log n)\) 的时间内将一个多项式转换成它的点值表示的算法。

什么是多项式的点值表示法

一个 \(n - 1\) 次的多项式 \(A(x)\)