由于某些东西比较复杂,本文略去了一些证明过程。

基本概念

一个环 R 上的关于 x 的多项式可以写作

在上一篇文章中,我们知道多项式有两种表示方法,这两种表示方法分别对应了求多项式卷积的两种方式,然而效率都比较低

其中 $a_i\in R$,表示每一项的系数,一个多项式最高非零项的次数称为这个多项式的次数

多项式的运算

多项式的线性运算:$A(x)\pm B(x)=\sum\limits_{i=0}^n(a_i\pm b_i)x^i$。

多项式的乘法:$A(x)B(x)=\sum\limits_{i=0}^n\sum\limits_{j=0}^na_ib_jx^{i+j}$,或者说,若 $A(x)B(x)=C(x)$,那么 $c_n=\sum\limits_{i=0}^na_ib_{n-i}$。前面的这个式子就是以后将会提到的卷积的形式

多项式的两种表示方法

分别是系数表示法点值表示法

系数表示法就是上文提到的形式。

而众所周知,一个 $n$ 次函数可以被 $n+1$ 个点唯一确定。这 $n+1$ 个点 $(x_i, y_i)$ 就叫做这个多项式的点值表示

接下来考虑多项式的乘法如何进行。

每一种表示方法都对应了一种多项式相乘的方法。

对于系数表示法,可以直接列竖式,即按照卷积的定义计算。这样时间复杂度为 $O(n^2)$。

对于点值表示法,可以将两个多项式带入一组相同的 $x_i$,将对应的 $y_i$ 相乘起来就得到了新多项式的点值表示。然而,在实际情况中一般都使用系数表示法,所以要用某种方法把点值转成系数。用高斯消元时间复杂度为 $O(n^3)$。

对于这两种方法也分别有优化的方法,下面的文章会讲到。