以下的难度顺序应该是递增的...
建议从前往后进行学习...
参考资料：
多项式求逆，多项式取模，多项式开方学习笔记-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\]
这个式子看起来非常的复杂，但其实理解之后还好（但其实还是推不出来...）。可以这样感性认知一下：

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

现在考虑求分母。
设多项式\(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)\)的。但也和众多的多项式运用一样，有一大坨常数...

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