题解：P4781 【模板】拉格朗日插值

· · 题解

稍微总结一下。

首先对于一个 n 次多项式必然可以由 n+1 个点唯一确定，于是若已知 n+1 个点，就可以通过某种途径算出所有点，拉格朗日插值提供了一种构造：

f(x)=\sum_{i=0}^{n}y_i \prod_{j \neq i} \frac{x-x_j}{x_i-x_j}

于是直接算就是 O(n^2) 的。

这里不讨论证明，来看看几种扩展。

一、横坐标连续

如 CF622E，让我们求： \displaystyle\ \sum_{i=1}^{n} i^k，直接求肯定爆炸，注意到这个式子实际上是 k+1 次多项式，因为：

\displaystyle\ \sum_{i=1}^{n} i^k=\frac{1}{k+1} \sum_{i=0}^k \binom{k+1}{i} B_i (n+1)^{k+1-i}

其中 B 是伯努利数。

所以可以利用伯努利数的生成函数套上多项式求逆 O(k \log k) 求。

所以容易列出式子：

f(n)=\sum_{i=1}^{n} i^k=\sum_{i=0}^{k+1}f(i) \prod_{j \neq i} \frac{n-j}{i-j}

后面那一块可拆开：\displaystyle \prod_{j \neq i} \frac{n-j}{i-j}=\prod_{j=1}^{i-1} \frac{n-j}{i-j} \times \prod_{j=i+1}^{n} \frac{n-j}{i-j}。

预处理前缀后缀积即可。

时间复杂度 O(k \log k) 或线性筛预处理做到 O(k) 不过其实优化不大。

二、求系数

如果遇到毒瘤题既要点值又要系数然后只给点值，难道拉格朗日就萎了吗？不！

回到式子： \displaystyle f(x)=\sum_{i=0}^{n}y_i \prod_{j \neq i} \frac{x-x_j}{x_i-x_j}，让我们尝试插出系数，分离常数 c_i= \cfrac{y_i}{ \displaystyle \prod_{i \neq j} x_i-x_j} 后，把剩下的 \displaystyle \prod_{i \neq j} x-x_j 设为 h_i，那么 \displaystyle f(x)=\sum_{i=0}^{n} c_i h_i，于是只用知道 h_i 的系数，先预处理一下 F(x)=\displaystyle \prod_{j=1}^{n} x-x_j 的系数，那么容易得到：(x-x_i)h_i=F，提出系数：[x^l]h_i=\dfrac{[x^{l-1}]h_{i}-[x^l]F}{x_i}，即可递推，可能上面一坨式子有点抽象，这里给出代码实现：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Mod=998244353;
const int N=1e6+7;
int n,k;
int x[N],y[N];
int F[N];
int a[N];
int h[N];
inline int ks(int a,int b)
{
    int res=1;
    while(b)
    {
        if(b&1) (res*=a)%=Mod;
        (a*=a)%=Mod;
        b>>=1; 
    }
    return res;
}
signed main()
{
    cin>>n>>k;
    for(int i=1;i<=n;i++)
        cin>>x[i]>>y[i];
    F[0]=1;
    for(int i=1;i<=n;i++)
    {
        for(int j=i-1;j>=0;j--)
        {
            (F[j+1]+=F[j])%=Mod;
            F[j]=F[j]*(Mod-x[i])%Mod;
        }
    }//求 F 系数
    for(int i=1;i<=n;i++)
    {
        int invx=ks(Mod-x[i],Mod-2);
        if(!invx) for(int j=0;j<n;j++) h[j]=F[j+1];//特判
        else
        {
            h[0]=1;
            for(int j=1;j<=n;j++) if(i!=j) h[0]=h[0]*(Mod-x[j])%Mod;
            for(int j=1;j<n;j++) h[j]=(F[j]-h[j-1]+Mod)%Mod*invx%Mod;
        }
        int c=1;
        for(int j=1;j<=n;j++) if(i!=j) c=c*(x[i]-x[j]+Mod)%Mod;
        c=y[i]*ks(c,Mod-2)%Mod;//c 就是上文 c_i
        for(int j=0;j<n;j++) a[j]=(a[j]+c%Mod*h[j]%Mod)%Mod;//每项系数加起来
    }
    int ans=0;
    for(int i=n-1;i>=0;i--)
        ans=(ans*k%Mod+a[i])%Mod;//秦九邵
    cout<<ans;
}

三、高科技

正常插是 O(n^2) 的，只有点值横坐标连续时才是 O(n) 的，那么点值横坐标不连续时，有没有快速的方法？嗯，还真有，不过有点超出讨论范围了，感兴趣的可以自己去看看。

四、实践

一些拉格朗日的题目并不是真的给你点求某个点值，而是答案是一个较低次的多项式，可以只算出几个点，然后通过拉格朗日来求，如这题，答案就是低次多项式，直接插即可，但更多的更加隐蔽，要仔细辨别。

不过有一个好方法！有些题可以设 f_{i,\dots} 代表在某些限制下答案的次数，然后跑 dp 即可。

五、总结

拉格朗日牛逼！