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

· · 题解

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

知道拉格朗日插值，你就能够在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];
}