Steven_MengのBlog

前置技能:单位根

我们有一个玄学函数$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}$

 评论