拉格朗日插值法

给定`n`个点`(x_i,y_i)`来确定一个多项式并将`k`代入求值

对于这个问题我们可以用高斯消元法以`\mathcal{O}(n^3)`的时间复杂度进行求解

但是有一种`\mathcal{O}(n^2)`的方法,名为拉格朗日插值法

$$ f(x)=\sum_{i=1}^{n}y_i\prod_{i \ne j}{\frac{x-x_j}{x_i-x_j}} $$

这东西就跟FFT一样烦,DP转移式推着推着发现需要用到拉格朗日插值法

为了方便理解,我们把上面那个式子等价地拆成两部分

$$ \ell_j(x)=\prod_{i=1,i \ne j}^{n}{\frac{x-x_i}{x_j-x_i}} $$

$$ P(x)=\sum_{i=1}^{n}y_i\ell_i(x) $$

先让我们看看第一个式子

$$ \ell_j(x)=\prod_{i=1,i \ne j}^{n}{\frac{x-x_i}{x_j-x_i}} $$

这个式子有一个性质

当`x=x_i`时$$ \ell_j (x) = 0 $$

当`x=x_j`时$$ \ell_j (x) = 1 $$

这时候我们想起第二个式子

$$ P(x)=\sum_{i=1}^{n}y_i\ell_i(x) $$

不难发现,当我们在代入第`i`个坐标时,除第`i`个分式外,所有分式的的值等于0

而代入第`i`个坐标后,分子分母完全相当,约去后只剩一下个`y_i`

说到这里想必有点难以理解,让我们来看一个例子

代入的三个点为`(1,4),(2,9),(3,16)`

$$ f(x) = 4\frac{(x-2)(x-3)}{(1-2)(1-3)} + 9\frac{(x-1)(x-3)}{(2-1)(2-3)} + 16\frac{(x-1)(x-2)}{(3-1)(3-2)} $$

代入后`f(x)=x^2+2x+1`

代码

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
39
40
41
42
43
44
45
46
47
48
49
50
#include <stdio.h>
#include <algorithm>

typedef long long LL;

const int N = 2e3;
const LL P = 998244353;

LL n, k, ans;
LL x[N + 5], y[N + 5];

LL pow(LL x, LL k)
{
LL res = 1;
while (k)
{
if (k & 1)
res = res * x % P;
x = x * x % P;
k >>= 1;
}
return res;
}

void Lagrange_Interpolation()
{
for (int i = 1; i <= n; i++)
{
LL a = 1, b = 1;
for (int j = 1; j <= n; j++)
{
if (i == j)
continue;
a = a * (k - x[j]) % P;
b = b * (x[i] - x[j]) % P;
}
ans = (ans + a * pow(b, P - 2) % P * y[i]) % P;
}
ans = (ans + P) % P;
}

int main()
{
scanf("%lld%lld", &n, &k);
for (int i = 1; i <= n; i++)
scanf("%lld%lld", &x[i], &y[i]);
Lagrange_Interpolation();
printf("%lld", ans);
return 0;
}

参考文献


  数论

评论

Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

×