专栏文章

题解：P4781 【模板】拉格朗日插值

封封禁用户
P4781题解参与者 5已保存评论 4

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
4 条
当前快照
1 份
快照标识符
@mio9hglp
此快照首次捕获于
2025/12/02 15:33
3 个月前
此快照最后确认于
2025/12/02 15:33
3 个月前
查看原文
稍微总结一下。
首先对于一个 nn 次多项式必然可以由 n+1n+1 个点唯一确定，于是若已知 n+1n+1 个点，就可以通过某种途径算出所有点，拉格朗日插值提供了一种构造：
f(x)=∑i=0nyi∏j≠ix−xjxi−xjf(x)=\sum_{i=0}^{n}y_i \prod_{j \neq i} \frac{x-x_j}{x_i-x_j}
于是直接算就是 O(n2)O(n^2) 的。
这里不讨论证明，来看看几种扩展。

一、横坐标连续

如 CF622E，让我们求： ∑i=1nik \displaystyle\ \sum_{i=1}^{n} i^k，直接求肯定爆炸，注意到这个式子实际上是 k+1k+1 次多项式，因为：
 ∑i=1nik=1k+1∑i=0k(k+1i)Bi(n+1)k+1−i\displaystyle\ \sum_{i=1}^{n} i^k=\frac{1}{k+1} \sum_{i=0}^k \binom{k+1}{i} B_i (n+1)^{k+1-i}
其中 BB 是伯努利数。
所以可以利用伯努利数的生成函数套上多项式求逆 O(klog⁡k)O(k \log k) 求。
所以容易列出式子：
f(n)=∑i=1nik=∑i=0k+1f(i)∏j≠in−ji−jf(n)=\sum_{i=1}^{n} i^k=\sum_{i=0}^{k+1}f(i) \prod_{j \neq i} \frac{n-j}{i-j}
后面那一块可拆开：∏j≠in−ji−j=∏j=1i−1n−ji−j×∏j=i+1nn−ji−j\displaystyle \prod_{j \neq i} \frac{n-j}{i-j}=\prod_{j=1}^{i-1} \frac{n-j}{i-j} \times \prod_{j=i+1}^{n} \frac{n-j}{i-j}。
预处理前缀后缀积即可。
时间复杂度 O(klog⁡k)O(k \log k) 或线性筛预处理做到 O(k)O(k) 不过其实优化不大。

二、求系数

如果遇到毒瘤题既要点值又要系数然后只给点值，难道拉格朗日就萎了吗？不！
回到式子：f(x)=∑i=0nyi∏j≠ix−xjxi−xj \displaystyle f(x)=\sum_{i=0}^{n}y_i \prod_{j \neq i} \frac{x-x_j}{x_i-x_j}，让我们尝试插出系数，分离常数 ci=yi∏i≠jxi−xjc_i= \cfrac{y_i}{ \displaystyle \prod_{i \neq j} x_i-x_j} 后，把剩下的 ∏i≠jx−xj\displaystyle \prod_{i \neq j} x-x_j 设为 hih_i，那么 f(x)=∑i=0ncihi\displaystyle f(x)=\sum_{i=0}^{n} c_i h_i，于是只用知道 hih_i 的系数，先预处理一下 F(x)=∏j=1nx−xjF(x)=\displaystyle \prod_{j=1}^{n} x-x_j 的系数，那么容易得到：(x−xi)hi=F(x-x_i)h_i=F，提出系数：[xl]hi=[xl−1]hi−[xl]Fxi[x^l]h_i=\dfrac{[x^{l-1}]h_{i}-[x^l]F}{x_i}，即可递推，可能上面一坨式子有点抽象，这里给出代码实现：
CPP
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int Mod=998244353;
const int N=1e6+7;
int n,k;
int x[N],y[N];
int F[N];
int a[N];
int h[N];
inline int ks(int a,int b)
{
	int res=1;
	while(b)
	{
		if(b&1) (res*=a)%=Mod;
		(a*=a)%=Mod;
		b>>=1; 
	}
	return res;
}
signed main()
{
	cin>>n>>k;
	for(int i=1;i<=n;i++)
		cin>>x[i]>>y[i];
	F[0]=1;
	for(int i=1;i<=n;i++)
	{
		for(int j=i-1;j>=0;j--)
		{
			(F[j+1]+=F[j])%=Mod;
			F[j]=F[j]*(Mod-x[i])%Mod;
		}
	}//求 F 系数
	for(int i=1;i<=n;i++)
	{
		int invx=ks(Mod-x[i],Mod-2);
		if(!invx) for(int j=0;j<n;j++) h[j]=F[j+1];//特判
		else
		{
			h[0]=1;
			for(int j=1;j<=n;j++) if(i!=j) h[0]=h[0]*(Mod-x[j])%Mod;
			for(int j=1;j<n;j++) h[j]=(F[j]-h[j-1]+Mod)%Mod*invx%Mod;
		}
		int c=1;
		for(int j=1;j<=n;j++) if(i!=j) c=c*(x[i]-x[j]+Mod)%Mod;
		c=y[i]*ks(c,Mod-2)%Mod;//c 就是上文 c_i
		for(int j=0;j<n;j++) a[j]=(a[j]+c%Mod*h[j]%Mod)%Mod;//每项系数加起来
	}
	int ans=0;
	for(int i=n-1;i>=0;i--)
		ans=(ans*k%Mod+a[i])%Mod;//秦九邵
	cout<<ans;
}

三、高科技

正常插是 O(n2)O(n^2) 的，只有点值横坐标连续时才是 O(n)O(n) 的，那么点值横坐标不连续时，有没有快速的方法？嗯，还真有，不过有点超出讨论范围了，感兴趣的可以自己去看看。

四、实践

一些拉格朗日的题目并不是真的给你点求某个点值，而是答案是一个较低次的多项式，可以只算出几个点，然后通过拉格朗日来求，如这题，答案就是低次多项式，直接插即可，但更多的更加隐蔽，要仔细辨别。
不过有一个好方法！有些题可以设 fi,…f_{i,\dots} 代表在某些限制下答案的次数，然后跑 dp 即可。

五、总结

拉格朗日牛逼！

评论

共 4 条评论，欢迎与作者交流。

正在加载评论...