FFT学习笔记

前置技能：单位根

我们有一个玄学函数$f(x)=\sum _{i=0}^{n-1} a_i x^i$

不妨换一个好看的形式：$f(x)= \\{a_0,a_1,a_2,...a_{n-1} \\}$

还有另一个玄学函数$g(x)=\\{b_0,b_1,b_2,...b_{n-1}\\}$

我们要计算$h$，其中$h_k=\sum_{i=0}^k a_i \times b_{n-i}$

一个典型的例子即是十进制整数乘法，此时$x=10$，$a_i,b_i$是每一位代表的值

不妨换一种思路，我们将一些未知数$x_0,x_1,x_2...x_{n-1}$带入$f,g$

此时我们使用点值表达式

$f(x)=\\{(x_0,f(x_0)),(x_1,f(x_1)),(x_2,f(x_2)),...,(x_{n-1},f(x_{n-1}))\\}$

$g(x)=\\{(x_0,g(x_0)),(x_1,g(x_1)),(x_2,g(x_2)),...,(x_{n-1},g(x_{n-1}))\\}$

我们就可以$O(n)$得到

$h(x)=\\{(x_0,f(x_0)·g(x_0)),(x_1,f(x_1)·g(x_1)),...,(x_{n-1},f(x_{n-1})·g(x_{n-1}))\\}$

于是可以高斯消元，求解系数。

等等，真的是这样的吗？高斯消元是$O(n^2)$的，时间复杂度没变。

考虑带入特殊的$x_0,x_1,x_2...x_{n-1}$