多项式简介

前置知识

FFT，多项式乘法

Basic Concepts

多项式的度

对于一个多项式 ，称其最高次项的次数为该多项式的 度（Degree） ，记作 。

多项式的逆元

对于多项式 ，若存在 满足：

则称 为 在模 意义下的 逆元（Inverse Element） ，记作 。

多项式的余数和商

对于多项式 ，存在 唯一 的 满足：

我们称 为 除 的 商（Quotient） ， 为 除 的 余数（Remainder） 。 亦可记作

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

对于一个多项式 ，可以将其对数函数看作其与麦克劳林级数的复合：

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

多项式的多点求值和插值

多项式的多点求值（Multi-point evaluation） 即给出一个多项式 和 个点 ，求

多项式的插值（Interpolation） 即给出 个点

求一个 次多项式 使得这 个点都在 上。

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

References

• Picks's Blog
• Miskcoo's Space