题解 P5158 【【模板】多项式快速插值】

想要解决这个问题，你得先知道[多项式多点求值](https://www.luogu.org/problemnew/show/P5050)和[拉格朗日插值](https://www.luogu.org/problemnew/show/P4781)。 知道拉格朗日插值，你就能够在$O(n^2)$内解决这个问题。但是这个显然是不能过去的。 不过，我们可以尝试优化插值的过程。 先看拉格朗日插值的过程。 $$f(x)=\sum_{i=1}^n y_i\prod_{j=1,j\not = i}^n \frac{x-x_j}{x_i-x_j}$$ $$=\sum_{i=1}^n \frac{y_i}{\prod_{j=1,j\not = i}^n(x_i-x_j)}*\prod_{j=1,j\not = i}^n(x-x_j)$$ 我们将它分成两个部分去计算。 先计算$\frac{y_i}{\prod_{j=1,j\not=i}^n (x_i-x_j)}$。上面是常数，因此我们只考虑下半部分。 设$\pi(x)=\prod_{i=1}^n (x-x_i)$，则我们要求的是$\frac{\pi(x_i)}{x-x_i}$。根据洛必达法则可以得到它就等于$\pi'(x_i)$。这部分利用上面的多点求值即可做到$O(n\log^2n)$。 然后，我们将式子拆开。 设$f_{l,r}(x)$表示$(x_l,y_l)$到$(x_r,y_r)$这些点插出来的多项式，则 $$f_{l,r}(x)=\sum_{i=l}^r \frac{y_i}{\pi'(x)}*\prod_{j=l,j\not = i}^r(x-x_j)$$ $$=[\prod_{j=mid+1}^r(x-x_j)]*\sum_{i=l}^{mid}\frac{y_i}{\pi'(x)}*[\prod_{j=l,j\not =i}^{mid}(x-x_j)]$$ $$+[\prod_{j=l}^{mid}(x-x_j)]*\sum_{i=mid+1}^r\frac{y_i}{\pi'(x)}*[\prod_{j=mid+1,j\not =i}^r(x-x_j)]$$ $$= [\prod_{j=mid+1}^r(x-x_j)]f_{l,mid}(x)+[\prod_{j=l}^{mid}(x-x_j)]f_{mid+1,r}(x)$$ 递归求解即可。时间复杂度$O(n\log^2n)$。 核心代码: ```cpp static int fst[MAXN]; void calcf(int*x,int l,int r,int lev) { if(l==r){pol[lev][0]=fst[l];return;} int mid=(l+r)>>1; calcf(x,l,mid,lev+1); calc(x,mid+1,r,0,0);//这是分治乘法 mul(pol[lev+1],solv[0][0],pol[lev],mid-l,r-mid);//这是多项式乘法 calcf(x,mid+1,r,lev+1); calc(x,l,mid,0,0); mul(pol[lev+1],solv[0][0],Q,r-mid-1,mid-l+1); Rep(i,0,r-l)pol[lev][i]=ad(pol[lev][i],Q[i]); } inline void getfunc(int*x,int*y,int*F,int n) { calc(x,1,n,0,0); Rep(i,0,n)pol[0][i]=solv[0][0][i]; Deriv(pol[0],pol[0],n);//这是求导 getnum(x,fst,1,n,0,n-1);//这是多点求值 Rep(i,1,n)fst[i]=(ll)y[i]*power(fst[i],mod-2)%mod; calcf(x,1,n,0);//主函数 Rep(i,0,n-1)F[i]=pol[0][i]; } ```