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

2019-02-10 20:46:05


想要解决这个问题,你得先知道多项式多点求值拉格朗日插值

知道拉格朗日插值,你就能够在$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)$。

核心代码:


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];
}