【学习笔记】拉格朗日插值法

好像初三的时候看选修4-6的课本看的一脸懵,这东西似乎是为数不多印象深刻的233

$\rm{0x01~~} Preface$

插值($\rm Interpolaton$) 在多项式域中可以看做是求值$(\rm Evaluation)$的逆运算。插值基于代数基本定理:

给定 $n+1$ 组确定的、本质不同的二元组$(x_i, y_i)$,满足 $F(x_i) = y_i$,可以逆向求出原 $n$ 次多项式 $F$。

而其实,拉格朗日插值公式本身是标准的 $\Theta(n^2)$ 算法:

或者不能称其为算法,是 $\Theta(n^2)$ 的运算过程或许会更准确一些。实际上该公式是构造出来的,所以没有多么繁琐的证明——

$\rm{0x02}~~\rm{Proof}$

$\rm Proof ~of~Existence$

我们定义 $F(x)$ 为一在实数域上的 $n-1$ 次多项式。

首先我们需要构造一个对于第 $i$ 个二元组的特殊多项式 $L_i(x)$,满足

那么我们所求的多项式 $F(x)$ 就可以这么计算出来:

这个式子保证了我们对应的 $n$ 个二元组,$F(x)=y$ 恒成立。

那么对于$L_i(x)$,我们考虑由我们对$L_i(x)$的定义可以得出其中不包含$x-x_i$这一因式。而由$L_i(x_i)=1$可知我们的比例系数

那么

从而


$\rm Proof~of~Uniqueness^{[1]}$

接下来要证明的是多项式 $L_i(x)$ 的唯一性

假设同时有两个实数域上的 $n-1$ 次多项式 $L_1(x),L_2(x)$ 满足

那么我们由作差法可以得出多项式 $L_{\Delta} = L_1 - L_2$ 在取所有的 $x_i$ 时,其值均为 $0$ 。那么一定会有多项式

满足

其中 $|$ 表示多项式整除。但是我们知道,对于 $L’$ 这个多项式,其次数为 $n$ ;而对于我们所定义的 $L_i(x)$ ,均为 $n-1$ 次的,从而 $L_{\Delta}$ 也是 $n-1$ 次多项式。所以我们可以得出

从而有

$\rm{0x03~\color{red}{C}\color{cyan}{o}\color{gold}{d}\color{green}{e}}$

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
//题号:Luogu4781
#include <cstdio>
#include <iostream>

#define MAXN 2020
#define LL long long
#define Mod 998244353

using namespace std ; LL Ans, xs ;
int N, i, j ; LL T, t, xv[MAXN], yv[MAXN] ;

inline LL expow(LL A, LL B){
LL res = 1 ;
while (B){
if (B & 1) (res *= A) %= Mod ;
B >>= 1, (A *= A) %= Mod ;
}
return res ;
}
int main(){
cin >> N >> T ;
for (i = 1 ; i <= N ; ++ i) scanf("%lld%lld", &xv[i], &yv[i]) ;
for (i = 1 ; i <= N ; ++ i){
t = 1 ;
for (j = 1 ; j <= N ; ++ j){
if (i == j) continue ;
(t *= (xv[i] - xv[j] + Mod)) %= Mod ;
}
t = expow(t, Mod - 2) ;
for (j = 1 ; j <= N ; ++ j){
if (i == j) continue ;
(t *= (T - xv[j] + Mod)) %= Mod ;
}
(t *= yv[i]) %= Mod, (Ans += t) %= Mod ;
// cout << Ans << endl ;
}
printf("%lld", Ans) ; return 0 ;
}

$0x04$ 一道水题

题意大概就是给出连续的一段 $x_0$ 和 $y_0$ ,算出多项式 $F(x)$ 在一个特定值 $x_0’$ 时的值。

注意到 $40 \%$ 的数据可以直接高消,列出 $n+1$ 个方程。同时还可以用朴素的拉格朗日插值法插出 $80pts$ 的好成绩。而对于 $100 \%$ 的数据,$n$ 是 $1e5$ 级别的,所以考虑预处理出一些东西。

观察拉格朗日插值公式的一般形式:

我们发现首先分子可以 $O(n)$ 预处理,而分母由于 $x_j$ 是连续的,所以

其中$\rm fac$表示求阶乘,$\rm{evenmark}(x)$ 是符号函数,当 $x$ 是偶数时返回 $1$,否则返回 $-1$ 。

于是我们就可以得出一个式子:

其中 $\frac{Pre}{x-x_i}$ 的缘由是分母上没有 $x-x_i$ 这一项。

取模啥的就小费马搞一搞即可,最终复杂度 $\Theta(n \log n)$ .

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
inline LL expow(LL A, LL B){
LL res = 1 ;
while (B){
if (B & 1) (res *= A) %= Mod ;
B >>= 1, (A *= A) %= Mod ;
}
return res % Mod ;
}
inline LL get_symbol(LL x){ return (!x ? 1 : Mod - 1) ; }
int main(){
cin >> N ; Fac[0] = qwq = 1 ;
for (i = 0 ; i <= N ; ++ i)
scanf("%lld", &base[i]), (Fac[i + 1] = Fac[i] * (i + 1)) %= Mod ;
cin >> T ; Ans = 0 ;
if (T <= N) return printf("%lld\n", base[T]) ;
for (i = 0 ; i <= N ; ++ i) (qwq *= (T - i + Mod)) %= Mod ;
for (i = 0 ; i <= N ; ++ i){
M = (N - i) & 1, _qwq = qwq * expow((T - i), Mod - 2) % Mod ;
t = expow(Fac[i] * Fac[N - i] % Mod, Mod - 2) % Mod ;
t = t * (get_symbol(M) * _qwq % Mod) % Mod, t = (t * base[i]) % Mod ;
(Ans += t) %= Mod ;
// cout << Ans << endl ;
}
printf("%lld\n", Ans) ; return 0 ;
}

$\rm{Reference}$