0
多项式部分简介
source link: https://xiaocairush.github.io/math/poly/intro/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
多项式部分简介
Basic Concepts¶
多项式的度¶
对于一个多项式 f(x)，称其最高次项的次数为该多项式的 度（Degree），记作 degf。
多项式的乘法¶
最核心的操作是两个多项式的乘法，即给定多项式 f(x) 和 g(x)：
f(x)=a0+a1x+⋯+anxn(1)g(x)=b0+b1x+⋯+bmxm(2)
要计算多项式 Q(x)=f(x)⋅g(x)：
Q(x)=∑i=0n∑j=0maibjxi+j=c0+c1x+⋯+cn+mxn+m
上述过程可以通过快速傅里叶变换在 O(nlogn) 下计算。
多项式的逆元¶
对于多项式 f(x)，若存在 g(x) 满足：
f(x)g(x)≡1(modxn)
则称 g(x) 为 f(x) 在模 xn 意义下的 逆元（Inverse Element），记作 f−1(x)。若要求 degg<n，则此时 g 唯一。
多项式的余数和商¶
对于多项式 f(x),g(x)，存在 唯一 的 Q(x),R(x) 满足：
f(x)=Q(x)g(x)+R(x)degR<degg
当 degf≥degg 时有 degQ=degf−degg，否则有 Q(x)=0。 我们称 Q(x) 为 g(x) 除 f(x) 的 商（Quotient），R(x) 为 g(x) 除 f(x) 的 余数（Remainder）。亦可记作
f(x)≡R(x)(modg(x))
多项式的对数函数与指数函数¶
对于一个多项式 f(x)，可以将其对数函数看作其与麦克劳林级数的复合：
ln(1−f(x))=−∑i=1+∞fi(x)iln(1+f(x))=∑i=1+∞(−1)i−1fi(x)i
其指数函数同样可以这样定义：
expf(x)=ef(x)=∑i=0+∞fi(x)i!
多项式的多点求值和插值¶
多项式的多点求值（Multi-point evaluation） 即给出一个多项式 f(x) 和 n 个点 x1,x2,…,xn，求
f(x1),f(x2),…,f(xn)
多项式的插值（Interpolation） 即给出 n+1 个点
(x0,y0),(x1,y1),…,(xn,yn)
求一个 n 次多项式 f(x) 使得这 n+1 个点都在 f(x) 上。
这两种操作的实质就是将多项式在 系数表示 和 点值表示 间转化。
参考资料与拓展阅读¶
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK