[学习笔记]拉格朗日插值法

pre

很早以前就知道这玩意儿，但是一直没有学。。。
然后突然看到了这东西，就顺便学了一下
然后发现十分简单

用途

（众所周知，n阶多项式能用n+1对不同的(x,y)来表示）
能将n阶多项式的点值表达式转换成系数表达式，主要就是用了构造法

实现

这个叫Joseph-Louis Lagrange的神仙把这个多项式分成了n个部分的和
使第$i$个部分$f_i(x_i)=y_i,f_i(x_j)=0(j̸=i)$
那么这个多项式$f_i$怎样构造
因为$f_i(x_j)=0$
所以多项式$f_i$一定有因式$(x_i-x_j)$
并且当$x=x_i$时$f_i(x_i)=y_i$
所以我们就构造出了
$$f_i(x)=y_i\times \prod _{1\le j\le n,j̸=i}\frac{x-x_i}{x_j-x_i}$$
最后只要把n个多项式加起来就好了
$$F=\sum _{i=1}^n(y_i\prod _{1\le j\le n,j̸=i}\frac{x-x_i}{x_j-x_i})$$
时间复杂度$\mathcal{O}(n^2)$

Code

下面是P4781 【模板】拉格朗日插值的代码

#include <cstdio>
#define MOD 998244353
#define N 2010

using namespace std;
typedef long long LL;
LL x[N], y[N];

inline LL qsm(LL x, int y) {
	if (y == 1) return x;
	LL t = qsm(x, y >> 1);
	if (y & 1) return t * t % MOD * x % MOD;
	else return t * t % MOD;
}

int main() {
	int n;
	LL k;
	scanf("%d%lld", &n, &k);
	for (int i = 1; i <= n; ++i) {
		scanf("%lld%lld", &x[i], &y[i]);
	}
	LL nowans = 0;
	for (int i = 1; i <= n; ++i) {
		LL ans = y[i];
		for (int j = 1; j <= n; ++j) {
			if (j != i) {
				ans = ans * (k - x[j]) % MOD * qsm(x[i] - x[j], MOD - 2) % MOD;
			}
		}
		nowans += ans;
		if (nowans < 0) nowans += MOD;
		if (nowans >= MOD) nowans -= MOD;
	}
	printf("%lld\n", nowans);
	return 0;
}