多项式简明百科全书

$0$、写在前面

为了方便本文的描述，定义如下内容：

我们说$f$是一个次数界为$n$（下文不严谨地简称为$n$次）的多项式，是指$f$是一个下标集合为$0,1,2,...,n-1$的数组，并代表：

$$\sum _{i=0}^{n-1}{f}_i{x}^i$$

这个多项式。

我们用$f(x_0)$代表多项式$f$在$x_0$处的值。

$1$、多项式乘法

利用$\mathrm{F}\mathrm{F}\mathrm{T}$就可以将多项式乘法的复杂度优化到$O(n\log n)$。由于其讲解较为繁琐并且已逐渐普及~~（想必读者也不是来学这个的）~~，因此略过$\mathrm{F}\mathrm{F}\mathrm{T}$以及同样普及的$\mathrm{N}\mathrm{T}\mathrm{T}$。

至于$\mathrm{M}\mathrm{T}\mathrm{T}$，我们可以将系数拆成$32768\cdot a+b$的形式缩小值域，将一个多项式拆为两个。做四次卷积以后，将得到的答案合并并取模即可。

当然$\mathrm{M}\mathrm{T}\mathrm{T}$还有利用$\mathrm{F}\mathrm{F}\mathrm{T}$模数计算再用中国剩余定理合并的做法，但第一种做法更加直观。

$2$、分治$\mathrm{F}\mathrm{F}\mathrm{T}$

有两种分治$\mathrm{F}\mathrm{F}\mathrm{T}$，先来讲比较简单的第一种。

如果我们有一个长度为$n$的数组$a$，并且希望求：

$$\prod _{i=0}^{n-1}(x+a_i)$$

直接按照暴力计算，是$O(n^2)$的（因为每一个只有两项，所以一次暴力乘法只有$O(n)$）。如果我们把乘法用$\mathrm{F}\mathrm{F}\mathrm{T}$来实现，我们就得到了$O(n^2\log n)$的优秀复杂度。

怎么做才会更快呢？

分治往往能带来更加优秀的复杂度。直接利用$\mathrm{F}\mathrm{F}\mathrm{T}$之所以慢，是因为相乘的两个多项式次数相差太大，这会非常浪费。

那我们不妨考虑先计算左半部分和右半部分的积。这是两个$O(n)$次的多项式，直接用$\mathrm{F}\mathrm{F}\mathrm{T}$在$O(n\log n)$的时间内相乘即可。那么我们的递归式就是：

$$T(n)=2T(n/2)+O(n\log n)$$

解得$T(n)=O(n{\log }^{2}n)$，复杂度得到了很大优化。

那么再来讲讲$dark$的第二种分治$\mathrm{F}\mathrm{F}\mathrm{T}$。

你有一个下标集合为$\{1,2,...,n\}$的数组$f$，你想要求一个下标集合为$\{0,1,2,...,n\}$的数组$g$，满足：

$$g_i=\sum _{j=1}^i{f}_j{g}_{i-j}$$

边界条件$g_0=1$。

看上去直接求好像有点困难，那么我们来考虑分治。我们把数组$g$拆为前后两半，显然后一半对前一半是没有影响的，直接递归求解前一半。求解完毕以后我们来计算前一半对后一半的贡献，这时我们直接根据上面的式子$\mathrm{F}\mathrm{F}\mathrm{T}$即可，因为此时前后的影响已经被我们用分治消除了。最后我们递归继续后一半的求解。

综上所述，递归式为：

$$T(n)=2T(n/2)+O(n\log n)$$

解得$T(n)=O(n{\log }^{2}n)$，复杂度较优秀。

$P.S.$第二个问题其实有复杂度更优秀的解法，可以参见下面的“多项式求逆”。但是分治的思想更加直观，并且有的类型并不能利用“多项式求逆”来做，因此分治$\mathrm{F}\mathrm{F}\mathrm{T}$的作用还是很大的。

$3$、多项式倍增（思想）

倍增是接下来对许多多项式问题求解的重要方法。

在多项式中可能有一些我们要求的多项式次数是无限的，那么一般我们只需要知道它的前$n$项，即$mod{x}^n$的结果即可。直接求解或许也比较困难，此时可以考虑倍增。

我们先用简单的方法求出$modx$的平凡情况，然后就只需要考虑如何从$mod{x}^k$ 的结果$\hat{f}$推到$mod{x}^{2k}$的结果$f$即可。一般来说，利用$(f-\hat{f}{)}^2\equiv 0(mod{x}^{2k})$这个性质就可以得到很方便的求解方法。

$4$、多项式求逆

多项式求逆是这样一个问题，已知一个$n$次多项式$f$，我们希望求一个$n$次多项式$g=f^{-1}$，即：

$$f\ast g\equiv 1(mod{x}^n)$$

显然要求$f$的常数项不为$0$。那么在$modx$意义下，直接求得$g_0=f_0^{-1}$。

现在我们考虑从$mod{x}^k$的结果$\hat{g}$推出$mod{x}^{2k}$的结果$g$。我们有：

$$(g-\hat{g}{)}^2\equiv 0(mod{x}^{2k})$$

把平方展开，得到：

$$g^2-2g\hat{g}+{\hat{g}}^2\equiv 0(mod{x}^{2k})$$

这个式子好像有点$dark$，但是我们已经知道$f\ast g\equiv 1(mod{x}^{2k})$，因此我们对等式两边同时乘以$f$，得到：

$$g-2\hat{g}+f{\hat{g}}^2\equiv 0(mod{x}^{2k})$$

移项，得：

$$g\equiv 2\hat{g}-f{\hat{g}}^2(mod{x}^{2k})$$

就可以直接进行倍增。递归式为$T(n)=T(n/2)+O(n\log n)$，解得$T(n)=O(n\log n)$。

多项式求逆也是很多多项式问题的基础，在接下来的几种多项式黑科技中起到了很大的作用。

那么再来举一个应用多项式求逆的例子，就是在之前的“分治$\mathrm{F}\mathrm{F}\mathrm{T}$”里提到的第二个问题。为了保持完整我们再陈述一遍：

你有一个下标集合为$\{1,2,...,n\}$的数组$f$，你想要求一个下标集合为$\{0,1,2,...,n\}$的数组$g$，满足：

$$g_i=\sum _{j=1}^i{f}_j{g}_{i-j}$$

边界条件$g_0=1$。

我们先想办法把上面的式子化成普通的卷积形式。我们把$j$的枚举范围从$1,2,...,i$改为卷积形式的$0,1,2,...,i$，此时我们发现多计算了$f_0{g}_i$这一项。那么我们不妨令$f_0=0$，我们就消去了这一项的贡献。同时注意到作为边界的$g_0$如果直接用这个卷积形式计算会得到$0$，那么我们可以强制将结果加$1$。经过这番操作卷积的答案就为$g$了。于是我们得到了非常优美的式子：

$$g=fg+1$$

我们移项，得到：

$$(1-f)g=1$$

利用多项式求逆求出$(1-f{)}^{-1}(mod{x}^{n+1})$，在两边同时乘上，于是得到了：

$$g\equiv \frac{1}{1-f}(mod{x}^{n+1})$$

由于我们只要知道$g$的前$n+1$项，因此$mod{x}^{n+1}$是没有关系的，于是我们就利用多项式求逆在$O(n\log n)$的时间内解决了这个问题。

$5$、多项式除法、取模

给你一个$n$次多项式$f$，以及一个$m$次多项式$g$（$n>m$），我们希望求一个$n-m+1$次多项式$q$以及一个$m-1$次多项式$r$，满足：

$$f=qg+r$$

那么我们称$q$为$f$除以$g$的商，而称$r$为$f$除以$g$的余数。

现在我们来考虑如何求$q$和$r$。我们先定义$n$次多项式$f$的一种变换$f^R$：

$$f^R=f(\frac{1}{x})\ast x^{n-1}$$

不难看出$f^R$即是将$f$的系数反转一下。因此我们可以在$O(n)$的时间内完成这个变换。

那么我们来推式子，我们不妨用$\frac{1}{x}$替换多项式内的$x$，这样的结果显然依旧正确：

$$f(\frac{1}{x})=q(\frac{1}{x})g(\frac{1}{x})+r(\frac{1}{x})$$

接着考虑在两边同乘$x^{n-1}$，得到：

$$f(\frac{1}{x})\ast x^{n-1}=q(\frac{1}{x})\ast x^{m-1}\ast g(\frac{1}{x})\ast x^{n-m}+r(\frac{1}{x})\ast x^{m-2}\ast x^{n-m+1}$$

不难发现我们已经有意为那个变换做好了准备，那么我们将四个多项式都用变换来代替：

$$f^R=q^R{g}^R+r^R\ast x^{n-m+1}$$

我们考虑消去最后一项，那么不妨把式子放到$mod{x}^{n-m+1}$的意义下。此时最后一项肯定为$0$，于是就消失了：

$$f^R\equiv q^R{g}^R(mod{x}^{n-m+1})$$

我们发现既然$q$是$n-m+1$次的，那么$q^R$也是$n-m+1$次的，$mod{x}^{n-m+1}$对其没有影响。于是我们求$g^R$的逆，就得到：

$$q^R\equiv \frac{f^R}{g^R}(mod{x}^{n-m+1})$$

于是我们就求得了$q^R$，然后简单地再做一次变换就得到了$q$。此时算$r$就很方便了，直接计算$f-qg$即可。

下面来讲一个多项式取模的应用——常系数齐次线性递推。

常系数齐次线性递推是指这样一个问题，给你一个数$k$，接着对于$i=1,2,...,k$，给出$a_i$，代表递推的系数。再对于$i=0,1,2,...,k-1$，给出$f_i$作为初始值，对于$i\ge k$，数列$f$满足：

$$f_i=\sum _{j=1}^k{a}_j\ast f_{i-j}$$

最后给你一个数$n$，需要求出$f_n$。$n$的范围很大。

显然直接递推是不可行的，我们不妨把思路放的巧妙一些。我们设有一个奇怪的$x$，其满足$x^i=f_i$（有点难理解，你不妨假设$x$只是一个代号，它根本不是一个数），那么它一定满足：

$$x^k=\sum _{i=1}^k{a}_j\ast x^{k-i}$$

于是我们移项，得到：

$$x^k-\sum _{i=1}^k{a}_i\ast x^{k-i}=0$$

我们将其当作一个$k+1$次的多项式来看待，那么如果我们将$x^n$对这个多项式取模，得到了商和余数。因为模多项式为$0$，因此商乘以这个模多项式的答案没有贡献，我们只关心这个余数。显然余数是一个$k$次多项式，你只需要知道$x^0,x^1,...,x^{k-1}$即可得到答案。而数列$f$的前$k$项是给出的，因此代入计算就可以了。因此整个过程只需要一个意义为卷积的乘法，以及意义为多项式取模的取模的快速幂就可以在$O(k\log k\log n)$的时间内完成这个操作。

$\mathrm{u}\mathrm{p}\mathrm{d}$：更详细的证明可以看这里 (opens new window)。

$6$、多项式求导、积分

这是两个很简单的变换，是为了下面的内容做好准备。

设$f$是一个$n$次多项式，那么$f$的导数$f^{\prime }$就是一个$n-1$次多项式，并且满足：

$$f_i^{\prime }=(i+1)f_{i+1}$$

直接$O(n)$计算即可。

设$f$是一个$n$次多项式，那么$f$的积分$\int f$就是一个$n+1$次多项式，并且满足：

$$\int f_i=\frac{f_{i-1}}{i}$$

边界条件$\int f_0=0$。

同样$O(n)$计算即可。

$7$、多项式$\ln$

事情开始变得诡异起来了。

多项式求$\ln$是这样一个问题，给你一个$n$次多项式$f$，满足$f_0=1$，你需要求一个$n$次多项式$g$，满足：

$$g\equiv \ln f(mod{x}^n)$$

看到这个是不是一下子有点懵啊...没关系，我们来冷静分析。函数$\ln (x)$的一个特点就是${\ln }^{\prime }(x)=\frac{1}{x}$，这就一下子好办了，我们把这个结论照搬到多项式上面去，利用复合函数的求导法则，对上面的等式两边求导，得到：

$$g^{\prime }\equiv \frac{f^{\prime }}{f}(mod{x}^n)$$

这是不是非常简单啊，直接多项式求逆就得到了$g^{\prime }$，那么我们再将等式两边积分，就得到：

$$g\equiv \int \frac{f^{\prime }}{f}(mod{x}^n)$$

不过还有一个小疑问，求导一次再积分一次不是会丢掉常数项吗，这怎么办呢。其实没关系，我们已经保证$f_0=1$，而$\ln 1=0$，因此$g$的常数项就是$0$。于是我们就做完了。

$8$、多项式牛顿迭代、泰勒展开（思想）

接下来我们讲一下多项式牛顿迭代和泰勒展开，为接下来的工作做准备。话说多项式真是强啊什么都能套上去。

先来讲牛顿迭代。

我们知道，如果我们希望在实数域内求得某个处处可导函数$f(x)$的零点的近似值，我们就可以用牛顿迭代来解决。我们随意选择一个初值，设其为$x_0$，然后开始迭代。每一次从$x_i$迭代到$x_{i+1}$，我们的精度会得到很大提升，迭代式子为：

$$x_{i+1}=x_i-\frac{f(x_i)}{f^{\prime }(x_i)}$$

其实就相当于$x_{i+1}$是$f(x)$在$x_i$处的这条切线和横轴的交点，可以自己推一下式子证明。

我们将牛顿迭代应用到多项式上，具体来说：

我们给出一个$n$次多项式$f$以及一个以多项式为参数，并且结果也是一个多项式的函数$G$，并希望计算出一个$n$次多项式$g$，满足：

$$G(g)\equiv f(mod{x}^n)$$

把问题简单转化一下，就是希望求得$G-f$的零点了。那么我们依然先求出$modx$意义下的简单结果，接着套用牛顿迭代的公式。设上一次迭代的答案为$\hat{g}$，我们就得到：

$$g=\hat{g}-\frac{G(\hat{g})-f}{G^{\prime }(\hat{g})}$$

为什么求导的时候多项式$f$会消失呢？这是因为$G$是关于多项式的函数，其导数反映的是当多项式变化时的变化幅度，因此不变的多项式$f$就被看作是常数项了。

同时我们可能还有一个疑问：牛顿迭代不是用来提高精度的吗？怎么在多项式上应用呢？我们感性理解一下，假设$\hat{g}$是$mod{x}^k$意义下的结果，那么迭代式子显然可以得到一个$2k$次多项式，此时我们给出结论：通过这个牛顿迭代的式子，我们可以得到$mod{x}^{2k}$意义下的结果。对它的证明将放到泰勒展开的讲解内。

于是我们就可以发现，利用牛顿迭代公式，我们可以做到类似倍增的效果。那么许多看似复杂的问题就可以解决了。

现在来讲一下多项式的泰勒展开。

我们刚刚已经得到了牛顿迭代在多项式上的应用，但是对于它的正确性，我们却是一知半解。幸好我们还有一种可以较简单的进行证明的方法：多项式泰勒展开。同时利用泰勒展开我们还可以获得一些问题求解的思路。

我们已经知道泰勒展开式为：

$$f(x)=\sum _{i=0}^{\mathrm{\infty }}\frac{f^{(i)}(x_0)}{i!}\ast (x-x_0{)}^i$$

我们可以证明其对以多项式为参数的函数也成立，这和一般情况是一样的。那么我们依然考虑之前牛顿迭代所讲的问题，我们以$mod{x}^k$意义下的答案$\hat{g}$代入$x_0$，求$mod{x}^{2k}$意义下的答案$g$，那么我们有：

$$G(g)-f\equiv G(\hat{g})-f+G^{\prime }(\hat{g})\ast (g-\hat{g})+...(mod{x}^{2k})$$

我们再次利用这个性质：$(g-\hat{g}{)}^2\equiv 0(mod{x}^{2k})$，那么泰勒展开式中除了前两项以外都变成了$0$，于是便不用再考虑后面了，得到：

$$G(g)-f\equiv G(\hat{g})-f+G^{\prime }(\hat{g})\ast (g-\hat{g})(mod{x}^{2k})$$

而我们又有$G(g)-f\equiv 0(mod{x}^{2k})$，于是左边就为$0$，我们移项得：

$$-G^{\prime }(\hat{g})\ast (g-\hat{g})\equiv G(\hat{g})-f(mod{x}^{2k})$$

两边同除$-G^{\prime }(\hat{g})$：

$$g-\hat{g}\equiv -\frac{G(\hat{g})-f}{G^{\prime }(\hat{g})}(mod{x}^{2k})$$

再将$\hat{g}$加到右边：

$$g\equiv \hat{g}-\frac{G(\hat{g})-f}{G^{\prime }(\hat{g})}(mod{x}^{2k})$$

我们此时发现这就是牛顿迭代的公式，于是就完成了对牛顿迭代正确性的证明。当然泰勒展开的作用不只是证明牛顿迭代，我们在做题时可能推出一个关于某个多项式的奇怪式子，如果你能发现它正好是一个常见函数的泰勒展开，就可以用专门求这个函数的方法来解决——例如我们即将要讲的$\exp$。

$9$、多项式$\exp$

多项式求$\exp$是这样一个问题，给你一个$n$次多项式$f$，满足$f_0=0$，你需要求一个$n$次多项式$g$，满足：

$$g=e^f(mod{x}^n)$$

由于我们已经有了关于$\ln$的经验，看到这个就不要害怕了（都是纸老虎）。

但是直接利用$\ln$求导积分的那一套似乎不可行，因为$\exp$的导数依然是$\exp$。但是我们正好可以利用求$\ln$是简单的这一点，结合刚刚所讲的牛顿迭代来解决这个问题。

我们可以很快把$\exp$转化为这样的问题：求一个$n$次多项式$g$，满足：

$$\ln g\equiv f(mod{x}^n)$$

那么问题转化为求$\ln g-f$的零点，我们套用牛顿迭代的公式来倍增。因为$f$的常数项一定是$0$，因此$g$的常数项就是$1$，那么对于已知的$mod{x}^k$意义下的答案$\hat{g}$，我们求$mod{x}^{2k}$意义下的答案$g$：

$$g=\hat{g}-\frac{\ln \hat{g}-f}{{\ln }^{\prime }\hat{g}}$$

而我们知道${\ln }^{\prime }\hat{g}={\hat{g}}^{-1}$，因此：

$$g=\hat{g}(1-\ln \hat{g}+f)$$

就可以倍增求得答案了。递归式为$T(n)=T(n/2)+O(n\log n)$，解得$T(n)=O(n\log n)$。

将$\exp$与$\ln$结合起来还可以得到多项式快速幂的$O(n\log n)$算法，具体来说：

给出一个$n$次多项式$f$，以及次数$k$，我们希望求：

$$f^k(mod{x}^n)$$

直接利用快速幂来计算，每次乘法是$O(n\log n)$的，一共$O(\log k)$次乘法，总复杂度为$O(n\log n\log k)$，因为$mod{x}^n$，所以可以选择在每次乘法以后只保留前$n$项。这是一个优秀的算法，但是下面的做法可以比这更优秀：

假设多项式$f$的系数不为$0$的最低次是$p$，那么我们可以先计算$(\frac{f}{a_p\ast x^p}{)}^k$，最后再简单地乘以$a_p^k\ast x^{pk}$即可，经过这样的处理，我们就保证了常数项为$1$，$\ln f$就是可以计算的。

那么套用数域上的结论：$x^k=e^{(\ln x)\ast k}$，我们得到：

$$f^k=e^{(\ln f)\ast k}$$

于是我们只要先求$\ln f$，再把每一项乘以$k$，最后进行一次$\exp$即可。如果之前有过处理，就像之前说的一样处理回去。这样的复杂度就是$O(n\log n)$的。

$10$、多项式开方

多项式开方是这样一个问题，给你一个$n$次多项式$f$，满足数域内存在某个数$t$，使得$t^2=f_0$，你需要求一个$n$次多项式$g$，满足：

$$g\equiv \sqrt{f}(mod{x}^n)$$

头回生二回熟，我们立刻可以发现这也可以利用牛顿迭代来解决对吧。我们现在是要求$g^2-f$的零点，那么$modx$时的答案就是$f_0$的平方根（我们已保证了这一点可以做到），考虑用牛顿迭代公式进行倍增：

$$g\equiv \hat{g}-\frac{{\hat{g}}^2-f}{({\hat{g}}^2{)}^{\prime }}(mod{x}^{2k})$$

显然$({\hat{g}}^2{)}^{\prime }=2\hat{g}$，那么把式子转化成好求的形式：

$$g\equiv \frac{1}{2}(\hat{g}+\frac{f}{\hat{g}})(mod{x}^{2k})$$

这样做的复杂度也是$O(n\log n)$。

$11$、多项式多点求值

事情好像更加毒瘤了。

我们可以利用$\mathrm{F}\mathrm{F}\mathrm{T}$在$O(n\log n)$的时间内求出$n$次多项式$f$在$n$个单位复数根处的值。那么我们自然还很好奇这样的一个问题：如果我随意给出$n$个点，有什么快速的方法可以求得它的值吗？答案是肯定的，利用下面的方法，我们可以在$O(n{\log }^{2}n)$的时间内求出一个$n$次多项式在任意$n$个点处的值。

首先给出一个简单的结论。回顾之前的多项式除法，对于$n$次多项式$f$，$f(x_0)$的值就是：

$$f(x_0)=fmod(x-x_0)$$

这个应该很好证明，$x-x_0$在$x=x_0$时值为$0$，因此它的倍数在求$x_0$时都为$0$，都没有影响，就只剩下一个常数，那就是答案。

现在的问题，就转化成对于下标集合为$\{0,1,2,...,n-1\}$的数组$a$，我们希望快速求得$fmod(x-a_i)$的值，其中$i=0,1,2,...,n-1$。

此时我们不妨考虑一下我们的老朋友分治。能否通过进行一些简单的处理，就能将$f$变成两个$\frac{n}{2}$次多项式递归求解呢？答案依然是肯定的。我们以左半部分为例，考虑将$f$变成：

$$fmod\prod _{i=0}^{\frac{n}{2}-1}(x-a_i)$$

这样的答案是不变的，因为在$x$等于左半部分任意的$a$值时，后面的连乘结果为$0$，没有影响，因此其倍数也不会有影响，而这式子是一个$\frac{n}{2}+1$次的多项式，$f$对其取模以后就得到了$\frac{n}{2}$次的多项式。对于右半部分，显然也是一样的。

再考虑如何快速求那个连乘。显然这是一个分治$\mathrm{F}\mathrm{F}\mathrm{T}$可以解决的问题，我们不妨先用$O(n{\log }^{2}n)$的时间预处理出每一层的连乘，接着再做一遍上述分治做法，我们在每一层的复杂度就是$O(n\log n)$，解得$T(n)=O(n{\log }^{2}n)$。

$12$、多项式多点插值

我们既然已经知道如何多点求值，自然也会好奇如何进行多点插值。这当然也是可以快速做到的，复杂度也是$O(n{\log }^{2}n)$。不过其过程会更加复杂一些。

假设我们已经知道$n$个互不相同的点值$(x_0,y_0),(x_1,y_1),...,(x_{n-1},y_{n-1})$，那么由这$n$个点插值出来的多项式一定是唯一的。那么我们不妨假设我们可以构造$n$次多项式${\ell }_i$，满足当$x$取$x_i$时值为$1$，取$x_j(j\ne i)$时值为$0$，那么显然这个多项式就是：

$$f=\sum _{i=0}^{n-1}{\ell }_i{y}_i$$

现在来考虑怎么构造它，这其实非常简单，只需：

$${\ell }_i=\prod _{j\ne i}\frac{x-x_j}{x_i-x_j}$$

发现当$x$取$x_j(j\ne i)$时分子必有一个为$0$，因此值为$0$。取$x_i$时分母分子相互抵消，答案就为$1$。于是我们有：

$$f=\sum _{i=0}^{n-1}\frac{y_i}{\prod _{j\ne i}(x_i-x_j)}\ast \prod _{j\ne i}(x-x_j)$$

直接根据定义计算显然是$O(n^2)$的，我们来考虑一下怎么做会更快。

我们先来计算$\prod _{j\ne i}(x_i-x_j)$这一部分如何。我们考虑计算出$n+1$次多项式$g$，满足：

$$g=\prod _{i=0}^{n-1}(x-x_i)$$

这可以用分治$\mathrm{F}\mathrm{F}\mathrm{T}$在$O(n{\log }^{2}n)$的时间内解决。那么对于每一个$i$，我们就是要求：

$$\frac{g(x_i)}{x-x_i}$$

可是这个式子分子分母都是$0$啊...这怎么办办...这时我们的救星出现了，它叫做洛必达法则：

对于函数$f(x)$，$g(x)$，如果当$x\to a$时，有$f(x)\to 0$，$g(x)\to 0$，那么有$\frac{f(a)}{g(a)}=\frac{f^{\prime }(a)}{g^{\prime }(a)}$

这其实也不难理解，两个趋近于$0$的数相除，我们用它们的变化率相除作为结果应该很自然。那么我们就可以利用洛必达法则，而$(x-x_i{)}^{\prime }=1$，于是我们对于$i$，要求的值就是$g^{\prime }(x_i)$。于是我们利用多项式多点求值，求出这$n$个答案，这样也是$O(n{\log }^{2}n)$的。

现在我们已经解决了第一部分，不妨用$v_i=\frac{y_i}{\prod _{j\ne i}(x_i-x_j)}$代替原来这一长串。于是我们现在要求的是：

$$\prod _{i=0}^{n-1}(v_i\ast \prod _{j\ne i}(x-x_j))$$

又到我们的老朋友出场了，我们再次利用分治来解决问题。我们先递归求解左右两半的子问题，接着以左半部分为例，不难发现我们需要的贡献就是左半部分的答案$\ast \prod _{i=\frac{n}{2}}^{n-1}(x-x_i)$，因为所有左半部分都是需要乘以它的。这又是一个分治$\mathrm{F}\mathrm{F}\mathrm{T}$的形式，于是先用$O(n{\log }^{2}n)$的时间处理好，那么我们的每一层就是$O(n\log n)$的。解得$T(n)=O(n{\log }^{2}n)$，我们终于解决了问题。

$13$、多项式三角函数

毒瘤$ing$...

多项式三角函数是这样一个问题，给你一个$n$次多项式$f$，满足$f_0=0$，你需要求两个$n$次多项式$g$和$h$，满足：

$$g\equiv \cos f(mod{x}^n),h\equiv \sin f(mod{x}^n)$$

$\cos$和$\sin$是最基本的三角函数，知道它们就可以知道所有三角函数。我们来考虑如何解决这个问题，从优美的欧拉公式入手：

$$e^{ix}=\cos (x)+i\sin (x)$$

我们将多项式$f$代入公式中，得到：

$$e^{if}=\cos f+i\sin f$$

那么我们可以将其代入复数域内计算，先将所有系数移到虚部再进行$\exp$得到结果，将得到的结果取实部和虚部即可。因为$f_0=0$，因此$i{f}_0=0$，可以进行$\exp$。

虽然需要在复数域内计算，但是多项式三角函数应该也是可以取模的，我们考虑对实部和虚部的系数分别取模，把每次卷积运算拆做四次，再将贡献算入结果的实部或虚部即可。