M_sea

「总结」拉格朗日插值
引入考虑这样一个问题:已知$n$次函数$f(x)$经过$n+1$个点$(x_0,y_0),(x_1,y_1),.....
扫描右侧二维码阅读全文
28
2019/01

「总结」拉格朗日插值

引入

考虑这样一个问题:已知$n$次函数$f(x)$经过$n+1$个点$(x_0,y_0),(x_1,y_1),...,(x_n,y_n)$,求$f(k)$。

显然可以用待定系数法求解,列出方程来套高斯消元,这样子是$O(n^3)$的。

事实上,我们可以用拉格朗日插值做到$O(n^2)$甚至$O(n)$。

简介

在数值分析中,拉格朗日插值法是以法国十八世纪数学家约瑟夫·拉格朗日命名的一种多项式插值方法。许多实际问题中都用函数来表示某种内在联系或规律,而不少函数都只能通过实验和观测来了解。如对实践中的某个物理量进行观测,在若干个不同的地方得到相应的观测值,拉格朗日插值法可以找到一个多项式,其恰好在各个观测的点取到观测到的值。这样的多项式称为拉格朗日(插值)多项式。数学上来说,拉格朗日插值法可以给出一个恰好穿过二维平面上若干个已知点的多项式函数

其实只有最后一句话是有用的。

公式

假设$\text{P}$是关于$x$的$n$次多项式,我们已经知道了$n$个点$(x_0,y_0),(x_1,y_1),...,(x_n,y_n)$,那么有:

$\large P(x)=\sum_{i=0}^{n}P(x_i)\prod_{j=0,j\ne i}^{n}\frac{x-x_j}{x_i-x_j}$

这样子是$O(n^2)$的。

如果取值连续,即已经知道$(0,y_0),(1,y_1),...,(n,y+n)$,那么有:

$\large P(x)=\sum_{i=0}^n(-1)^{n-i}P(i)\frac{x(x-1)(x-2)...(x-n)}{(n-i)!\,i!\,(x-i)}$

这样子是$O(n)$的。

证明不会,这东西背下来救星了

代码

//Luogu4781 【模板】拉格朗日插值
//It is made by M_sea
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

const int N=2000+10;
const int MOD=998244353;

int x[N],y[N];

inline int fastpow(int a,int b,int ans=1) {
    for (;b;b>>=1,a=1ll*a*a%MOD)
        if (b&1) ans=1ll*ans*a%MOD;
    return ans;
}

int main() {
    int n=read()-1,k=read(),ans=0;
    for (re int i=0;i<=n;++i) x[i]=read(),y[i]=read();
    for (re int i=0;i<=n;++i) {
        int tmp=1;
        for (re int j=0;j<=n;++j) {
            if (i==j) continue;
            tmp=1ll*tmp*(k-x[j])%MOD*fastpow(x[i]-x[j],MOD-2)%MOD;
        }
        ans=(ans+1ll*y[i]*tmp)%MOD;
    }
    printf("%d\n",(ans+MOD)%MOD);
    return 0;
}

其它应用:拉格朗日插值+DP

一般是写出一个$O(nm)$的$\texttt{DP}$,然后$m$特别大,于是就布星。

那么就假装$f[i][j]$是关于$j$的多项式,再手推一下次数,比如为$x$。

那么只要算出前$0\sim x$项,然后用拉格朗日插值去求答案救星了。

是不是很抽象?来一道例题。

CF995F Cowmpany Cowmpensation

首先容易写出$O(nD)$的树形$\texttt{DP}$,但是$D$特别大,于是就布星。

设$f[i][j]$表示以$i$为根的子树,$i$的工资是$j$的方案数。

然后假装$f[i][j]$是关于$j$的$i$次多项式,发现好像是对的。

所以只要算出$f[1][0\sim n]$,然后用拉格朗日插值去求$f[1][D]$救星了。

因为取值连续,所以时间复杂度是$O(n^2+n\log MOD)$的。

最后修改:2019 年 03 月 23 日 06 : 05 PM

发表评论