常见导数

多项式积分

泰勒展开

泰勒展开可以将一个函数表示为无穷级数的形式:

其中比较常用的是处的展开,也称为麦克劳林展开:

多项式牛顿迭代

已知函数,求多项式,使得

考虑倍增。假设我们求出了使得

首先注意到,因此,即他们的低位是一样的。

考虑将处泰勒展开:

注意到把低位都减没了。的最低次数项的次数都是,因此可以直接忽略了。即

因为,化简得到

也可以简记为

牛迭与多项式牛迭

接触过牛顿迭代的读者会知道,对于一个连续且单调的函数,我们要求的近似解,则迭代的公式为

牛顿迭代可以直观理解:如果当前位置的点值和导数点值同号,说明在根的右边;否则说明在根的左边。

那么多项式牛顿迭代又怎么直观理解呢?

多项式环是没有数轴的说法的。不过我们可以把它看作是向一个多项式逼近的过程,就像泰勒展开一样。变成,代入,它的增量是不断变小(收敛)的。如果的话是发散的,这不在我们讨论的范围中。也就是说在的时候,多项式的高次项对点值的影响就越小。因此倍增牛迭可以理解为是添加高次项来逼近多项式。

接下来我们来看一下多项式牛顿迭代的应用。

多项式求逆

假设我们要求的逆。设

那么问题转化为了求满足的解。应用牛顿迭代得到

那么使用 FFT/NTT 即可在的时间内计算。

多项式开方

假设我们要求的平方根。设。应用牛顿迭代得到

时间复杂度

多项式 ln

对于一个多项式的定义是什么?

首先我们考虑在原点的泰勒展开:

这样一来,我们就可以定义

换句话说对于的多项式,我们把它整理成的形式,就可以理解为上述定义。

那么对于一个多项式,如何求出?考虑复合函数求导:

两边同时积分得到

这样就可以用多项式求逆来计算了。这样计算的一个问题是,求导再积分后,常数项就没了。这时如果就会比较好办,这时

注:

所以不要尝试用来理解……

多项式 exp

对于一个多项式的含义是什么?

仿照的含义,我们将在原点泰勒展开得到

因此可以得到

考虑求。设。应用牛顿迭代得到

时间复杂度

模板代码

参考文献

泰勒级数 - 维基百科

多项式牛顿迭代 - OI Wiki

浅谈生成函数之 OGF

牛顿迭代法在多项式运算的应用 - Miskcoo’s Space

导数列表 - 维基百科

指数函数 - 维基百科