多项式与点值式

正常\(\text{DFT/IDFT}\)是构造一个特殊的点值式，即\(x_i=\omega_{n}^i\)

如果能通过题目条件构造出来这样的点值，就可以直接\(\text{DFT/IDFT}\)

那如果不能的话。。。。。

多项式多点求值

一个多项式\(F(x)\)我们求它在\(x_0,x_0,\cdots x_{m-1}\)上的点值

核心是分治+多项式取模

对于当前分治区间\([l,r]\in[0,m-1]\)

我们需要快速构造一个长度为\(\frac{r-l+1}{2}\)的多项式进入分治区间

那么构造\(G(x)_{l,r}=\prod_l^r(1-x_i)\)

由于\(G(x_l)_{l,r}=\cdots=G(x_r)_{l,r}=0\)

所以可以将\(F(x)\)对于\(G(x)_{l,mid}\)和\(G(x)_{mid+1,r}\)分别取模之后进入递归子区间

递归到\([l=r]\)时，\(F(x)\)只剩下常数项

需要被访问的\(G(x)\)可以预先跑一遍分治NTT求出

那么复杂度就是\(O(n\log ^2n)\)

\[\ \]

---

多项式快速插值

对于点对\((x_i,y_i)\)

多项式拉格朗日插值的式子是

\[\begin{aligned}F(x) = \sum_{i=0}^{n-1} y_i \prod_{i\ne j} \frac{x-x_j}{x_i-x_j}\end{aligned} \]

那么需要快速求出\(\prod \frac{1}{x_i-x_j}\)

构造多项式\(G(x)=\prod (x-x_i)\)

那么\(\prod (x_i-x_j)=\frac{G}{x-x_i}(x_i)\)

由于\(G(x),x-x_i\)在\(x_i\)上的点值均为\(0\)

带入洛必达法则\(\frac{G}{x-x_i}(x_i)=\frac{G'}{(x-x_i)'}(x_i)=G'(x_i)\)

那么求出\(G'(x_i)\)多项式多点求值即可

剩下那一部分可以简单地分治合并上来，\([l=r]\)时，多项式是一个常数

合并上来时

\([l,mid]\)的答案补上\(\prod_{mid+1}^r (x-x_i)\)

\([mid+1,r]\)的答案补上\(\prod_{l}^{mid} (x-x_i)\)

即复杂度为\(O(n\log ^2n)\)

垃圾评测机模板题卡了好久

---