FFT入门
FFT(快速傅里叶变换)是上个学期学会的东西，由于接下来要玩母函数，所以现在写篇博客复习一下。 FFT可以在 O ( n log n ) O ( n log n ) 的时间内完成多项式乘法。 问题 给定两个十进制数（ 10 5 10 5 位），求它们的乘积。 不妨把它归为一个 多项式乘积 的问题：每一位都是一个系数，那么 1234*2333 就变成了： ( x 3 + 2 x 2 + 3 x + 4 ) ∗ ( 2 x 3 + 3 x 2 + 3 x + 3 ) ( x 3 + 2 x 2 + 3 x + 4 ) ∗ ( 2 x 3 + 3 x 2 + 3 x + 3 ) 对于多项式乘积问题，显然跑 O ( n 2 ) O ( n 2 ) 的朴素高精度乘法是过不了的。考虑我们计算 a × b a × b 的方式：令 X X 为答案，则有： X n = n ∑ i = 0 a i × b n − i X n = ∑ i = 0 n a i × b n − i 因此，我们做的事情是 直接计算答案的每一位 。现在我们换一种思路。 点值表达 之前我们使用的 ( x 5 + 233 x 3 + x ) ( x 5 + 233 x 3 + x ) 这种表达方式，被称为 系数表达 。因为它给出了系数向量： ( 1 , 0 , 233 , 0 , 1 , 0 ) ( 1 , 0 , 233 , 0 , 1 , 0 ) 。 但是考虑这样一个事实： 给定 n n 个点，可以唯一确定一个 n − 1 n − 1 次多项式函数。 至于如何确定，有 高斯消元 和 拉格朗日插值法 。 因此我们拥有了一种全新的表达多项式的方式：点值表达。给出 n + 1 n + 1 个点，可以表达一个多项式。 例如： ( 0 , 0 ) , ( 1 , 1 ) , ( 2 , 4 ) ( 0 , 0 ) , ( 1 , 1 ) , ( 2 , 4 ) 是多项式 ( x 2 ) ( x 2 ) 的一种点值表达。 一个多项式有无数组点值表达 。 有什么用呢？ 考虑多项式的加法 A + B A + B ，生成的多项式的点值表达，可以由 A A 和 B B 的点值表达得到。在 A A 和 B B 上取相同的一些 x x ，求出对应的点值表达： ...