Codeforces 86D - Powerful array
题目链接：Codeforces 86D
快速傅立叶变换（FFT）学习笔记
经典问题：记 \(f(x) = \sum_{i=0}^{n} a_i x^i\)，\(g(x) = \sum_{i=0}^{m} b_i x^i\)，其中\(1\leq n, m \leq 10^5\)，求\(f \cdot g (x)\)。
显然如果我们做朴素的多项式乘法，时间复杂度是 \(O(nm)\) 的。我们可以使用快速傅立叶变换（FFT）在 \(O(c \log c)\) 的时间内解决此问题，其中 \(c\) 是不小于 \(n+m\) 的最小的 \(2\) 的幂。
本文是笔者学习FFT的笔记和一些思考，不推荐作为教程食用。