跳转至

多项式部分简介

Basic Concepts

多项式的度

对于一个多项式 f\left(x\right),称其最高次项的次数为该多项式的度(Degree),记作 \operatorname{deg}{f}.

多项式的逆元

对于多项式 f\left(x\right),若存在 g\left(x\right)满足:

\begin{aligned} f\left(x\right)g\left(x\right)&\equiv 1\pmod{x^{n}}\\ \operatorname{deg}{g}&\leqslant\operatorname{deg}{f} \end{aligned}

则称 g\left(x\right)f\left(x\right)在模 x^{n}意义下的逆元(Inverse Element),记作 f^{-1}\left(x\right).

多项式的余数和商

对于多项式 f\left(x\right),g\left(x\right),存在唯一Q\left(x\right),R\left(x\right)满足:

\begin{aligned} f\left(x\right)&=Q\left(x\right)g\left(x\right)+R\left(x\right)\\ \operatorname{deg}{Q}&=\operatorname{deg}{f}-\operatorname{deg}{g}\\ \operatorname{deg}{R}&<\operatorname{deg}{g} \end{aligned}

我们称 Q\left(x\right)g\left(x\right)f\left(x\right)商(Quotient),R\left(x\right)g\left(x\right)f\left(x\right)余数(Remainder).

亦可记作

f\left(x\right)\equiv R\left(x\right)\pmod{g\left(x\right)}

多项式的对数函数与指数函数

对于一个多项式 f\left(x\right),可以将其对数函数看作其与麦克劳林级数的复合:

\ln{\left(1-f\left(x\right)\right)}=-\sum_{i=1}^{+\infty}\frac{f^{i}\left(x\right)}{i}

其指数函数同样可以这样定义:

\exp{f\left(x\right)}=e^{f\left(x\right)}=\sum_{i=0}^{+\infty}\frac{f^{i}\left(x\right)}{i!}

多项式的多点求值和插值

多项式的多点求值(Multi-point evaluation) 即给出一个多项式 f\left(x\right)n个点 x_{1},x_{2},...,x_{n},求

f\left(x_{1}\right),f\left(x_{2}\right),...,f\left(x_{n}\right)

多项式的插值(Interpolation) 即给出 n+1个点

\left(x_{0},y_{0}\right),\left(x_{1},y_{1}\right),...,\left(x_{n},y_{n}\right)

求一个 n次多项式 f\left(x\right)使得这 n+1个点都在 f\left(x\right)上.

这两种操作的实质就是将多项式在系数表示点值表示间转化.

References

Picks's Blog

Miskcoo's Space


评论