多项式常用操作归纳

目录多项式求逆多项式取模多项式的多点求值多项式的多点插值nlog(n)^3的做法nlog(n)^2的做法以下的难度顺序应该是递增的...建议从前往后进行学习...参考资料:多项式求逆,多项式取模,多项式开方学习笔记-byKsCla多项式的多点求值与快速插值-byMiskcoo多项式多点求值和插值-byZZQ@多项式求逆其实就是改变了模运算的形式,然后用到多项式上来。大概是这个形式:\[A(x)*B...

目录

  • 多项式求逆
  • 多项式取模
  • 多项式的多点求值
  • 多项式的多点插值
    • nlog(n)^3的做法
    • nlog(n)^2的做法

以下的难度顺序应该是递增的...
建议从前往后进行学习...
参考资料:

多项式求逆,多项式取模,多项式开方 学习笔记-by KsCla
多项式的多点求值与快速插值-by Miskcoo
多项式多点求值和插值-by ZZQ


@

多项式求逆

其实就是改变了模运算的形式,然后用到多项式上来。大概是这个形式:
\[A(x)*B(x) \equiv 1 (mod\ x^n)\]
其中A(x)和B(x)都是多项式,A(x)是输入的多项式,B(x)是我们需要求的在模x^n意义下的多项式。

可以看出B(x)的最高次项的次数一定是小于n的。

考虑如何进行求解。
设当前需要求解的是下边这个式子的B(x):
\[A(x)*B(x)\equiv 1(mod\ x^n)-----(1)\]
那么我们考虑已经求得下边这个式子的B'(x):
\[A(x)*B'(x)\equiv 1(mod\ x^{\lceil\frac{n}{2}\rceil})-----(2)\]
(以下请自行脑补上取整)
那么我们将第一个式子变化为:
\[A(x)*B(x)\equiv 1(mod\ x^{\frac{n}{2}})-----(3)\]
然后将(3)-(2)有:
\[A(x)*(B(x)-B'(x))\equiv 0(mod\ x^{\frac{n}{2}})-----(4)\]
最后将两边同时乘上B(x)(式子(1)):
\[B(x)-B'(x)\equiv 0(mod\ x^{\frac{n}{2}})-----(5)\]
这个式子就比较好了。因为要回到mod x^n的意义上来,我们考虑将这个式子进行平方。
假设\(x^k\ mod\ x^{\frac{n}{2}}\)中的k>=n/2,那么等于0,在k2,(n/2)2之后还是一样的;如果k < n/2,那么模完之后的次数为j的话,在k2,(n/2)2之后,j也乘上了2.
于是就可以得到:
\[B(x)*B(x)-2*B(x)*B'(x) B'(x)^2\equiv 0(mod\ x^n)\]
再利用之前的套路,让两边同时乘上A(x)(式子(1)),就有:
\[B(x)-2*B'(x) A(x)*B'(x)^2\equiv 0(mod\ x^n)\]
移项后就有:
\[B(x)\equiv 2*B'(x)-A(x)*B'(x)^2(mod\ x^n)\]
然后就可以通过不断地分治,求得子问题后,进行NTT乘法,求得B(x)。
总的时间复杂度是\(O(nlog_n^2)\),然后还要乘上一个巨大的常数...

有了多项式求逆之后我们就有了一个比较有利的工具了。

多项式取模

这个部分大概就是对于多项式求逆元的一个应用了。之后再补上吧。

多项式的多点求值

在有了以上的两个工具之后,我们就可以进行更加复杂的操作了。
(剩下两部分的讲解可能有些偏差,如果感觉有和自己想得不一样的地方,可以参考之前给出的链接)

进入正题。

首先,多项式的多点求值主要是解决这样一个问题:给定一个多项式A(x)和n个点\(x_0,x_1,x_2,x_3,x_4...x_n\),然后要你求出\(A(x_0),A(x_1),A(x_2)...A(x_n)\)
不难想到有一个n^2的算法,就是直接对于每一个\(x_i\)枚举每一项加和得到\(A(x_i)\)
但是这显然是不够的。
我们考虑这样一个方法:
假设当前的问题是有一个x[]集合为\(x_0,x_1...x_n\),然后多项式为A(x)。
将我们需要带进去的x[]集合划分为两个部分:
\[LX[]=x_0,x_1,...x_{\lfloor\frac{n}{2}\rfloor}\]
\[RX[]=x_{\lfloor\frac{n}{2}\rfloor 1},...,x_n\]
然后再构造这样两个多项式LP(x),RP(x):
\[LP(x)=\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}(x-x_i)\]
\[RP(x)=\prod_{i=\lfloor\frac{n}{2}\rfloor 1}^{n-1}(x-x_i)\]
有了这两个多项式之后,我们再让A(x)分别模LP(x)和RP(x)(可以类比实数的运算),这里就只讨论LP(x),RP(x)的部分的处理是一模一样的。
那么就有:
\[A(x)=D(x)*LP(x) A'(x)\]
\(x\in LX[]\)时,LP(x)由它的定义可得是等于0的。那么就直得到了A'(x)。
再把它写成模运算的形式:
\[A(x)\equiv A'(x)(mod\ LP(x))\]
然后就利用多项式的模运算求解就可以了。然后再讲A'(x)传给下一层,在底层(n=0)的时候就是一个常数了,就把这个位置的点值求出来了。

其实这里在参考博客中有一个问题似乎没有说清楚,就是怎么求LP(x)。虽然有定义,但是那个是无法利用的。根据我的理解,应该是先进行一次预处理,对于每一层需要用到的LP(x)和RP(x)都先用分治FFT求出来:就是在底层的时候直接返回,然后在将两个区间进行合并的时候,就对两个区间的LP(x)进行卷积(乘法),然后就求出所有可能用到的LP(x)和RP(x)了。

然后预处理的复杂度大概是\(O(nlog_n)\)的,求答案的复杂度大概也是\(O(nlog_n)\)的,但是同样也是常数巨大,无论怎么优化,都很容易T。所以小心为上。

多项式的多点插值

多点插值其实是这样的一个问题:
给定一个点的集合:\(Point=(x_0,y_0),(x_1,y_1),(x_2,y_2)...(x_n,y_n)\),然后要求你求出一个多项式A(x),使得\(y_0=A(x_0),y_1=A(x_1),y_2=A(x_2)...y_n=A(x_n)\)

目前我看见的有两种做法。一种是\(O(nlog_n^3)\)的,还有一种是\(O(nlog_n^2)\)的。

nlog(n)^3的做法

其实有一点像多项式的多点求值的方法在进行讨论,但千万注意概念不要混淆了,特别是在看参考博客的时候。
还是先假设当前的点的集合为{\((x_0,y_0),(x_1,y_1),(x_2,y_2)...(x_n,y_n)\)},然后我们需要求的多项式为A(x)。
首先将点的集合分为两个部分:
\[LX=(x_0,y_0),(x_1,y_1),...,(x_{\lfloor\frac{n}{2}\rfloor},y_{\lfloor\frac{n}{2}\rfloor})\]
\[RX=(x_{\lfloor\frac{n}{2}\rfloor 1},y_{\lfloor\frac{n}{2}\rfloor 1}),...,(x_{n-1},y_{n-1 })\]
然后我们在构造一个“似曾相识”的多项式:
\[P(x)=\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}(x-x_i)\]
然后再让A(x)去模P(x)(果然和上面的很像):
\[A(x)=A_1(x)P(x) A_2(x)\]
但是其中的A(x),A1(x),A2(x)都是不知道的。
先不管,将RX集合递归下去求A1(x)是不需要任何的前提条件的,那么我们就先递归把A1(x)求出来吧。
回溯回来之后,我们发现还有另外一半的RX点集没有使用。上面我们设出来的式子,对于LX和RX应该都是成立的,所以说就有以下的等式:
\[对于(x_i,y_i)\in RX,y_i=A_1(x_i)P(x_i) A_2(x_i)\]
\[->A_1(x_i)=\frac{y_i-A_2(x_i)}{P(x_i)}\]
那么就利用多点求值快速求出A2(xi)和P(xi)了,然后可以求出A1(x)对应的n/2个点值,进而继续递归进行求解了。
这样子处理完了之后,A1(x),A2(x)就都被求出来了,那么再根据上面的式子,就能够直接把A(x)给求出来了。
但是先不慌,看一波时间复杂度:还需要利用多点求值!!那么就是\(O(log_n*nlog^2n)=O(nlog^3n)\),再乘上一大坨常数,这个方法几乎与O(n^2)无异了...

nlog(n)^2的做法

首先有一个结论,也就是拉格朗日插值:
\[F(x)=\sum_{i=1}{n}\frac{\prod_{j!=i}(x-x_j)}{\prod_{j!=i}(x_i-x_j)}y_i\]
这个式子看起来非常的复杂,但其实理解之后还好(但其实还是推不出来...)。可以这样感性认知一下:

假设对于带进去的是\(x_i\),那么当k!=i的时候,分母的上面总会枚举到j使得j==i,然后就是0了,根本不用看分母了;然后k==i的时候,且j!=i(k),然后你就会发现分子和分母是同一个式子,那么自然就等于1了,再乘上后面的\(y_i\),自然就是\(y_1\)了。

这样子就能够理解上面的式子了。

现在考虑求分母。
设多项式\(M(x)=\prod_{i=1}^{n}(x-x_i)\),然后很容易就能够看出拉格朗日插值的式子中的di的分子就是\(\frac{M(x)}{x-x_i}\),但是你会发现当期你要求的就是\(\frac{M(x_i)}{(x_i-x_i)}\),分子与分母都是0!!!然而利用我们学过的高中知识,也就是洛必达法则,然后就可以得到其实这就是M'(x)。这个时候,聪明的读者就会发现M'(x)在全局都是一样的,就可以利用多点求值快速求出答案了。

然后我们设每一项的系数就是\(val_i=\frac{y_i}{\prod_{}(x_i-x_j)}\),正式开始考虑如何求这个多项式了。再设\(LP(x)=\prod_{i=1}^{\lfloor\frac{n}{2}\rfloor}(x-x_i)\)\(RP(x)=\prod_{i=\lfloor\frac{n}{2}\rfloor 1}^{n}(x-x_i)\) ,然后原多项式(即F(x))就可以表示为:
\[F(x)=\sum_{i=1}^{\lfloor\frac{n}{2}\rfloor}(val_i*\prod_{j!=i}^{j<=\lfloor\frac{n}{2}\rfloor}(x-x_j)R(x)) \sum_{i=\lfloor\frac{n}{2}\rfloor 1}^{n}(val_i*\prod_{j!=i}^{j>\lfloor\frac{n}{2}\rfloor}(x-x_j)L(x))\]
然后我们可以发现左右两边几乎形成了一个可以递归地式子(左边算的就是原式中的<=n/2的部分,右边算的就是>n/2的部分)。特别需要注意的是,需要将其与拉格朗日插值区分开来,且需要将val[i]也化到递归地下一层去,那么递归地底层就是l==r的时候,这个时候应该返回val[l]。
然后分析一波时间复杂度。大概是\(O(nlogn*logn)\)的。但也和众多的多项式运用一样,有一大坨常数...

各种实现的话,目前由于博主效率有限,后面会慢慢补上来的...

源文地址:https://www.guoxiongfei.cn/cntech/6766.html