浅谈拉格朗日插值

先丢个板子
P4781 【模板】拉格朗日插值

其实就是给你 n n n个点，可以唯一确定一个 n − 1 n-1 n−1次的多项式 f ( x ) f(x) f(x)
然后再给你一个 k k k问 f ( k ) f(k) f(k)是多少
然后我们发现多项式可以表示成这个形式

手玩一下可以发现，它就是构造了一个多项式，使得当 k = x [ i ] k=x[i] k=x[i]的时候只有 y [ i ] y[i] y[i]会留下来，其他的都连乘都会变成0
然后这个东西其实就是原多项式
然后直接套这条柿子就可以过掉模板题了

code:

#include<bits/stdc++.h>
#define N 1000005
#define int long long
#define mod 998244353
using namespace std;
int qpow(int x, int y) {
	int ret = 1;
	for(; y; y >>= 1, x = x * x % mod) if(y & 1) ret = ret * x % mod;
	return ret;
}
int n, k, x[N], y[N];
signed main() {
	scanf("%lld%lld", &n, &k);
	for(int i = 1; i <= n; i ++) scanf("%lld%lld", &x[i], &y[i]);
	int ans = 0;
	for(int i = 1; i <= n; i ++) {
		int pi = 1;
		for(int j = 1; j <= n; j ++) if(j != i) pi = pi * (x[i] - x[j] + mod) % mod;
		pi = qpow(pi, mod - 2);//分母
		for(int j = 1; j <= n; j ++) if(j != i) pi = pi * (k - x[j] + mod) % mod;//分子
		ans = (ans + y[i] * pi % mod) % mod;//加起来
	}
	printf("%lld", ans);
	return 0;
}

优化
我们考虑自变量值域连续的情况，即x=1~n
可以发现上面那条柿子

下面就变成了 f a c [ i − 1 ] ∗ f a c [ n − i ] fac[i - 1] * fac[n - i] fac[i−1]∗fac[n−i]
注意一点， n − i n-i n−i如果是奇数要取负
然后分子可以直接预处理一个 p r e [ i ] = p r e [ i − 1 ] ∗ ( k − x [ i ] ) pre[i] = pre[i - 1] * (k - x[i]) pre[i]=pre[i−1]∗(k−x[i])和 suf 然后乘起来就是分子

下面的题题解后面再补
luogu P4593 [TJOI2018]教科书般的*
P4463 [集训队互测2012] calc
CF995F Cowmpany Cowmpensation