前置技能：单位根

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

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

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

我们要计算hh，其中hk=∑i=0kai×bn−ih_k=\sum_{i=0}^k a_i \times b_{n-i}

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

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

此时我们使用点值表达式

f(x)=(x0,f(x0)),(x1,f(x1)),(x2,f(x2)),...,(xn−1,f(xn−1))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)=(x0,g(x0)),(x1,g(x1)),(x2,g(x2)),...,(xn−1,g(xn−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)O(n)得到

h(x)=(x0,f(x0)⋅g(x0)),(x1,f(x1)⋅g(x1)),...,(xn−1,f(xn−1)⋅g(xn−1))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(n2)O(n^2)的，时间复杂度没变。

考虑带入特殊的x0,x1,x2...xn−1x_0,x_1,x_2...x_{n-1}