\(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\)、多项式乘法
利用\(\rm FFT\)就可以将多项式乘法的复杂度优化到\(O(n\log n)\)。由于其讲解较为繁琐并且已逐渐普及(想必读者也不是来学这个的),因此略过\(\rm FFT\)以及同样普及的\(\rm NTT\)。
至于\(\rm MTT\),我们可以将系数拆成\(32768\cdot a+b\)的形式缩小值域,将一个多项式拆为两个。做四次卷积以后,将得到的答案合并并取模即可。
当然\(\rm MTT\)还有利用\(\rm FFT\)模数计算再用中国剩余定理合并的做法,但第一种做法更加直观。
\(2\)、分治\(\rm FFT\)
有两种分治\(\rm FFT\),先来讲比较简单的第一种。
如果我们有一个长度为\(n\)的数组\(a\),并且希望求:
\[\prod_{i=0}^{n-1}(x+a_i)\]
直接按照暴力计算,是\(O(n^2)\)的(因为每一个只有两项,所以一次暴力乘法只有\(O(n)\))。如果我们把乘法用\(\rm FFT\)来实现,我们就得到了\(O(n^2\log n)\)的优秀复杂度。
怎么做才会更快呢?
分治往往能带来更加优秀的复杂度。直接利用\(\rm FFT\)之所以慢,是因为相乘的两个多项式次数相差太大,这会非常浪费。
那我们不妨考虑先计算左半部分和右半部分的积。这是两个\(O(n)\)次的多项式,直接用\(\rm FFT\)在\(O(n\log n)\)的时间内相乘即可。那么我们的递归式就是:
\[T(n)=2T(n/2)+O(n\log n)\]
解得\(T(n)=O(n\log ^2n)\),复杂度得到了很大优化。
那么再来讲讲\(dark\)的第二种分治\(\rm FFT\)。
你有一个下标集合为\(\{1,2,...,n\}\)的数组\(f\),你想要求一个下标集合为\(\{0,1,2,...,n\}\)的数组\(g\),满足:
\[g_i=\sum_{j=1}^{i}f_jg_{i-j}\]
边界条件\(g_0=1\)。
看上去直接求好像有点困难,那么我们来考虑分治。我们把数组\(g\)拆为前后两半,显然后一半对前一半是没有影响的,直接递归求解前一半。求解完毕以后我们来计算前一半对后一半的贡献,这时我们直接根据上面的式子\(\rm FFT\)即可,因为此时前后的影响已经被我们用分治消除了。最后我们递归继续后一半的求解。
综上所述,递归式为:
\[T(n)=2T(n/2)+O(n\log n)\]
解得\(T(n)=O(n\log^2 n)\),复杂度较优秀。
\(P.S.\)第二个问题其实有复杂度更优秀的解法,可以参见下面的“多项式求逆”。但是分治的思想更加直观,并且有的类型并不能利用“多项式求逆”来做,因此分治\(\rm FFT\)的作用还是很大的。
\(3\)、多项式倍增(思想)
倍增是接下来对许多多项式问题求解的重要方法。
在多项式中可能有一些我们要求的多项式次数是无限的,那么一般我们只需要知道它的前\(n\)项,即\(\bmod x^n\)的结果即可。直接求解或许也比较困难,此时可以考虑倍增。
我们先用简单的方法求出\(\bmod x\)的平凡情况,然后就只需要考虑如何从\(\bmod x^k\)
的结果\(\widehat f\)推到\(\bmod x^{2k}\)的结果\(f\)即可。一般来说,利用\((f-\widehat f)^2\equiv 0 (\bmod x^{2k})\)这个性质就可以得到很方便的求解方法。
\(4\)、多项式求逆
多项式求逆是这样一个问题,已知一个\(n\)次多项式\(f\),我们希望求一个\(n\)次多项式\(g=f^{-1}\),即:
\[f*g\equiv 1(\bmod x^n)\]
显然要求\(f\)的常数项不为\(0\)。那么在\(\bmod x\)意义下,直接求得\(g_0=f_0^{-1}\)。
现在我们考虑从\(\bmod x^k\)的结果\(\widehat g\)推出\(\bmod x^{2k}\)的结果\(g\)。我们有:
\[(g-\widehat g)^2\equiv 0(\bmod x^{2k})\]
把平方展开,得到:
\[g^2-2g\widehat g+\widehat g^2\equiv 0(\bmod x^{2k})\]
这个式子好像有点\(dark\),但是我们已经知道\(f*g\equiv 1(\bmod x^{2k})\),因此我们对等式两边同时乘以\(f\),得到:
\[g-2\widehat g+f\widehat g^2\equiv 0(\bmod x^{2k})\]
移项,得:
\[g\equiv 2\widehat g-f\widehat g^2(\bmod x^{2k})\]
就可以直接进行倍增。递归式为\(T(n)=T(n/2)+O(n\log n)\),解得\(T(n)=O(n\log n)\)。
多项式求逆也是很多多项式问题的基础,在接下来的几种多项式黑科技中起到了很大的作用。
那么再来举一个应用多项式求逆的例子,就是在之前的“分治\(\rm FFT\)”里提到的第二个问题。为了保持完整我们再陈述一遍:
你有一个下标集合为\(\{1,2,...,n\}\)的数组\(f\),你想要求一个下标集合为\(\{0,1,2,...,n\}\)的数组\(g\),满足:
\[g_i=\sum_{j=1}^{i}f_jg_{i-j}\]
边界条件\(g_0=1\)。
我们先想办法把上面的式子化成普通的卷积形式。我们把\(j\)的枚举范围从\(1,2,...,i\)改为卷积形式的\(0,1,2,...,i\),此时我们发现多计算了\(f_0g_i\)这一项。那么我们不妨令\(f_0=0\),我们就消去了这一项的贡献。同时注意到作为边界的\(g_0\)如果直接用这个卷积形式计算会得到\(0\),那么我们可以强制将结果加\(1\)。经过这番操作卷积的答案就为\(g\)了。于是我们得到了非常优美的式子:
\[g=fg+1\]
我们移项,得到:
\[(1-f)g=1\]
利用多项式求逆求出\((1-f)^{-1}(\bmod x^{n+1})\),在两边同时乘上,于是得到了:
\[g\equiv \frac{1}{1-f}(\bmod x^{n+1})\]
由于我们只要知道\(g\)的前\(n+1\)项,因此\(\bmod 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})*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})*x^{n-1}=q(\frac{1}{x})*x^{m-1}*g(\frac{1}{x})*x^{n-m}+r(\frac{1}{x})*x^{m-2}*x^{n-m+1}\]
不难发现我们已经有意为那个变换做好了准备,那么我们将四个多项式都用变换来代替:
\[f^R=q^Rg^R+r^R*x^{n-m+1}\]
我们考虑消去最后一项,那么不妨把式子放到\(\bmod x^{n-m+1}\)的意义下。此时最后一项肯定为\(0\),于是就消失了:
\[f^R\equiv q^Rg^R(\bmod x^{n-m+1})\]
我们发现既然\(q\)是\(n-m+1\)次的,那么\(q^R\)也是\(n-m+1\)次的,\(\bmod x^{n-m+1}\)对其没有影响。于是我们求\(g^R\)的逆,就得到:
\[q^R\equiv \frac{f^R}{g^R}(\bmod 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\geq k\),数列\(f\)满足:
\[f_i=\sum_{j=1}^k a_j*f_{i-j}\]
最后给你一个数\(n\),需要求出\(f_n\)。\(n\)的范围很大。
显然直接递推是不可行的,我们不妨把思路放的巧妙一些。我们设有一个奇怪的\(x\),其满足\(x^i=f_i\)(有点难理解,你不妨假设\(x\)只是一个代号,它根本不是一个数),那么它一定满足:
\[x^k=\sum_{i=1}^k a_j*x^{k-i}\]
于是我们移项,得到:
\[x^k-\sum_{i=1}^k a_i*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)\)的时间内完成这个操作。
\(\rm upd\):更详细的证明可以看这里。
\(6\)、多项式求导、积分
这是两个很简单的变换,是为了下面的内容做好准备。
设\(f\)是一个\(n\)次多项式,那么\(f\)的导数\(f'\)就是一个\(n-1\)次多项式,并且满足:
\[f'_i=(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(\bmod x^n)\]
看到这个是不是一下子有点懵啊...没关系,我们来冷静分析。函数\(\ln(x)\)的一个特点就是\(\ln'(x)=\frac{1}{x}\),这就一下子好办了,我们把这个结论照搬到多项式上面去,利用复合函数的求导法则,对上面的等式两边求导,得到:
\[g'\equiv \frac{f'}{f}(\bmod x^n)\]
这是不是非常简单啊,直接多项式求逆就得到了\(g'\),那么我们再将等式两边积分,就得到:
\[g\equiv \int \frac{f'}{f}(\bmod 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'(x_i)}\]
其实就相当于\(x_{i+1}\)是\(f(x)\)在\(x_i\)处的这条切线和横轴的交点,可以自己推一下式子证明。
我们将牛顿迭代应用到多项式上,具体来说:
我们给出一个\(n\)次多项式\(f\)以及一个以多项式为参数,并且结果也是一个多项式的函数\(G\),并希望计算出一个\(n\)次多项式\(g\),满足:
\[G(g)\equiv f(\bmod x^n)\]
把问题简单转化一下,就是希望求得\(G-f\)的零点了。那么我们依然先求出\(\bmod x\)意义下的简单结果,接着套用牛顿迭代的公式。设上一次迭代的答案为\(\widehat g\),我们就得到:
\[g=\widehat g-\frac{G(\widehat g)-f}{G'(\widehat g)}\]
为什么求导的时候多项式\(f\)会消失呢?这是因为\(G\)是关于多项式的函数,其导数反映的是当多项式变化时的变化幅度,因此不变的多项式\(f\)就被看作是常数项了。
同时我们可能还有一个疑问:牛顿迭代不是用来提高精度的吗?怎么在多项式上应用呢?我们感性理解一下,假设\(\widehat g\)是\(\bmod x^k\)意义下的结果,那么迭代式子显然可以得到一个\(2k\)次多项式,此时我们给出结论:通过这个牛顿迭代的式子,我们可以得到\(\bmod x^{2k}\)意义下的结果。对它的证明将放到泰勒展开的讲解内。
于是我们就可以发现,利用牛顿迭代公式,我们可以做到类似倍增的效果。那么许多看似复杂的问题就可以解决了。
现在来讲一下多项式的泰勒展开。
我们刚刚已经得到了牛顿迭代在多项式上的应用,但是对于它的正确性,我们却是一知半解。幸好我们还有一种可以较简单的进行证明的方法:多项式泰勒展开。同时利用泰勒展开我们还可以获得一些问题求解的思路。
我们已经知道泰勒展开式为:
\[f(x)=\sum_{i=0}^{\infty}\frac{f^{(i)}(x_0)}{i!}*(x-x_0)^i\]
我们可以证明其对以多项式为参数的函数也成立,这和一般情况是一样的。那么我们依然考虑之前牛顿迭代所讲的问题,我们以\(\bmod x^k\)意义下的答案\(\widehat g\)代入\(x_0\),求\(\bmod x^{2k}\)意义下的答案\(g\),那么我们有:
\[G(g)-f\equiv G(\widehat g)-f+G'(\widehat g)*(g-\widehat g)+...(\bmod x^{2k})\]
我们再次利用这个性质:\((g-\widehat g)^2\equiv 0(\bmod x^{2k})\),那么泰勒展开式中除了前两项以外都变成了\(0\),于是便不用再考虑后面了,得到:
\[G(g)-f\equiv G(\widehat g)-f+G'(\widehat g)*(g-\widehat g)(\bmod x^{2k})\]
而我们又有\(G(g)-f\equiv 0(\bmod x^{2k})\),于是左边就为\(0\),我们移项得:
\[-G'(\widehat g)*(g-\widehat g)\equiv G(\widehat g)-f(\bmod x^{2k})\]
两边同除\(-G'(\widehat g)\):
\[g-\widehat g\equiv -\frac{G(\widehat g)-f}{G'(\widehat g)}(\bmod x^{2k})\]
再将\(\widehat g\)加到右边:
\[g\equiv \widehat g-\frac{G(\widehat g)-f}{G'(\widehat g)}(\bmod x^{2k})\]
我们此时发现这就是牛顿迭代的公式,于是就完成了对牛顿迭代正确性的证明。当然泰勒展开的作用不只是证明牛顿迭代,我们在做题时可能推出一个关于某个多项式的奇怪式子,如果你能发现它正好是一个常见函数的泰勒展开,就可以用专门求这个函数的方法来解决——例如我们即将要讲的\(\exp\)。
\(9\)、多项式\(\exp\)
多项式求\(\exp\)是这样一个问题,给你一个\(n\)次多项式\(f\),满足\(f_0=0\),你需要求一个\(n\)次多项式\(g\),满足:
\[g=e^f(\bmod x^n)\]
由于我们已经有了关于\(\ln\)的经验,看到这个就不要害怕了(都是纸老虎)。
但是直接利用\(\ln\)求导积分的那一套似乎不可行,因为\(\exp\)的导数依然是\(\exp\)。但是我们正好可以利用求\(\ln\)是简单的这一点,结合刚刚所讲的牛顿迭代来解决这个问题。
我们可以很快把\(\exp\)转化为这样的问题:求一个\(n\)次多项式\(g\),满足:
\[\ln g\equiv f(\bmod x^n)\]
那么问题转化为求\(\ln g-f\)的零点,我们套用牛顿迭代的公式来倍增。因为\(f\)的常数项一定是\(0\),因此\(g\)的常数项就是\(1\),那么对于已知的\(\bmod x^k\)意义下的答案\(\widehat g\),我们求\(\bmod x^{2k}\)意义下的答案\(g\):
\[g=\widehat g-\frac{\ln \widehat g-f}{\ln'\widehat g}\]
而我们知道\(\ln' \widehat g=\widehat g^{-1}\),因此:
\[g=\widehat g(1-\ln\widehat 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(\bmod x^n)\]
直接利用快速幂来计算,每次乘法是\(O(n\log n)\)的,一共\(O(\log k)\)次乘法,总复杂度为\(O(n\log n\log k)\),因为\(\bmod x^n\),所以可以选择在每次乘法以后只保留前\(n\)项。这是一个优秀的算法,但是下面的做法可以比这更优秀:
假设多项式\(f\)的系数不为\(0\)的最低次是\(p\),那么我们可以先计算\((\frac{f}{a_p*x^p})^k\),最后再简单地乘以\(a_p^k*x^{pk}\)即可,经过这样的处理,我们就保证了常数项为\(1\),\(\ln f\)就是可以计算的。
那么套用数域上的结论:\(x^k=e^{(\ln x)*k}\),我们得到:
\[f^k=e^{(\ln f)*k}\]
于是我们只要先求\(\ln f\),再把每一项乘以\(k\),最后进行一次\(\exp\)即可。如果之前有过处理,就像之前说的一样处理回去。这样的复杂度就是\(O(n\log n)\)的。
\(10\)、多项式开方
多项式开方是这样一个问题,给你一个\(n\)次多项式\(f\),满足数域内存在某个数\(t\),使得\(t^2=f_0\),你需要求一个\(n\)次多项式\(g\),满足:
\[g\equiv \sqrt f(\bmod x^n)\]
头回生二回熟,我们立刻可以发现这也可以利用牛顿迭代来解决对吧。我们现在是要求\(g^2-f\)的零点,那么\(\bmod x\)时的答案就是\(f_0\)的平方根(我们已保证了这一点可以做到),考虑用牛顿迭代公式进行倍增:
\[g\equiv \widehat g-\frac{\widehat g^2-f}{(\widehat g^2)'}(\bmod x^{2k})\]
显然\((\widehat g^2)'=2\widehat g\),那么把式子转化成好求的形式:
\[g\equiv \frac{1}{2}(\widehat g+\frac{f}{\widehat g})(\bmod x^{2k})\]
这样做的复杂度也是\(O(n\log n)\)。
\(11\)、多项式多点求值
事情好像更加毒瘤了。
我们可以利用\(\rm FFT\)在\(O(n\log n)\)的时间内求出\(n\)次多项式\(f\)在\(n\)个单位复数根处的值。那么我们自然还很好奇这样的一个问题:如果我随意给出\(n\)个点,有什么快速的方法可以求得它的值吗?答案是肯定的,利用下面的方法,我们可以在\(O(n\log^2 n)\)的时间内求出一个\(n\)次多项式在任意\(n\)个点处的值。
首先给出一个简单的结论。回顾之前的多项式除法,对于\(n\)次多项式\(f\),\(f(x_0)\)的值就是:
\[f(x_0)=f\bmod (x-x_0)\]
这个应该很好证明,\(x-x_0\)在\(x=x_0\)时值为\(0\),因此它的倍数在求\(x_0\)时都为\(0\),都没有影响,就只剩下一个常数,那就是答案。
现在的问题,就转化成对于下标集合为\(\{0,1,2,...,n-1\}\)的数组\(a\),我们希望快速求得\(f\bmod (x-a_i)\)的值,其中\(i=0,1,2,...,n-1\)。
此时我们不妨考虑一下我们的老朋友分治。能否通过进行一些简单的处理,就能将\(f\)变成两个\(\frac{n}{2}\)次多项式递归求解呢?答案依然是肯定的。我们以左半部分为例,考虑将\(f\)变成:
\[f\bmod \prod_{i=0}^{\frac{n}{2}-1}(x-a_i)\]
这样的答案是不变的,因为在\(x\)等于左半部分任意的\(a\)值时,后面的连乘结果为\(0\),没有影响,因此其倍数也不会有影响,而这式子是一个\(\frac{n}{2}+1\)次的多项式,\(f\)对其取模以后就得到了\(\frac{n}{2}\)次的多项式。对于右半部分,显然也是一样的。
再考虑如何快速求那个连乘。显然这是一个分治\(\rm FFT\)可以解决的问题,我们不妨先用\(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\neq i)\)时值为\(0\),那么显然这个多项式就是:
\[f=\sum_{i=0}^{n-1}\ell_i y_i\]
现在来考虑怎么构造它,这其实非常简单,只需:
\[\ell_i=\prod_{j\neq i}\frac{x-x_j}{x_i-x_j}\]
发现当\(x\)取\(x_j(j\neq i)\)时分子必有一个为\(0\),因此值为\(0\)。取\(x_i\)时分母分子相互抵消,答案就为\(1\)。于是我们有:
\[f=\sum_{i=0}^{n-1}\frac{y_i}{\prod_{j\neq i}(x_i-x_j)}*\prod_{j\neq i}(x-x_j)\]
直接根据定义计算显然是\(O(n^2)\)的,我们来考虑一下怎么做会更快。
我们先来计算\(\prod_{j\neq i}(x_i-x_j)\)这一部分如何。我们考虑计算出\(n+1\)次多项式\(g\),满足:
\[g=\prod_{i=0}^{n-1}(x-x_i)\]
这可以用分治\(\rm FFT\)在\(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'(a)}{g'(a)}\)
这其实也不难理解,两个趋近于\(0\)的数相除,我们用它们的变化率相除作为结果应该很自然。那么我们就可以利用洛必达法则,而\((x-x_i)'=1\),于是我们对于\(i\),要求的值就是\(g'(x_i)\)。于是我们利用多项式多点求值,求出这\(n\)个答案,这样也是\(O(n\log^2n)\)的。
现在我们已经解决了第一部分,不妨用\(v_i=\frac{y_i}{\prod_{j\neq i}(x_i-x_j)}\)代替原来这一长串。于是我们现在要求的是:
\[\prod_{i=0}^{n-1}\Big(v_i*\prod_{j\neq i}(x-x_j)\Big)\]
又到我们的老朋友出场了,我们再次利用分治来解决问题。我们先递归求解左右两半的子问题,接着以左半部分为例,不难发现我们需要的贡献就是左半部分的答案\(*\prod_{i=\frac{n}{2}}^{n-1}(x-x_i)\),因为所有左半部分都是需要乘以它的。这又是一个分治\(\rm FFT\)的形式,于是先用\(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(\bmod x^n),h\equiv \sin f(\bmod x^n)\]
\(\cos\)和\(\sin\)是最基本的三角函数,知道它们就可以知道所有三角函数。我们来考虑如何解决这个问题,从优美的欧拉公式入手:
\[e^{ix}=\cos(x)+i\sin(x)\]
我们将多项式\(f\)代入公式中,得到:
\[e^{if}=\cos f+i\sin f\]
那么我们可以将其代入复数域内计算,先将所有系数移到虚部再进行\(\exp\)得到结果,将得到的结果取实部和虚部即可。因为\(f_0=0\),因此\(if_0=0\),可以进行\(\exp\)。
虽然需要在复数域内计算,但是多项式三角函数应该也是可以取模的,我们考虑对实部和虚部的系数分别取模,把每次卷积运算拆做四次,再将贡献算入结果的实部或虚部即可。