LG4781 【模板】拉格朗日插值

【模板】拉格朗日插值

题目描述

由小学知识可知，$n$个点$(x_i,y_i)$可以唯一地确定一个多项式

现在，给定$n$个点，请你确定这个多项式，并将$k$代入求值

求出的值对$998244353$取模

说明

$n \leq 2000 \; \; \; x_i,y_i,k \leq 998244353$

自为风月马前卒的分析

拉格朗日插值法

众所周知，\(n + 1\)个\(x\)坐标不同的点可以确定唯一的最高为\(n\)次的多项式。在算法竞赛中，我们常常会碰到一类题目，题目中直接或间接的给出了\(n+1\)个点，让我们求由这些点构成的多项式在某一位置的取值

一个最显然的思路就是直接高斯消元求出多项式的系数，但是这样做复杂度巨大\((n^3)\)且根据算法实现不同往往会存在精度问题

而拉格朗日插值法可以在\(n^2\)的复杂度内完美解决上述问题

假设该多项式为\(f(x)\), 第\(i\)个点的坐标为\((x_i, y_i)\)，我们需要找到该多项式在\(k\)点的取值

根据拉格朗日插值法

\[f(k) = \sum_{i = 0}^{n} y_i \prod_{i \not = j} \frac{k - x[j]}{x[i] - x[j]}
\]

乍一看可能不是很好理解，我们来举个例子理解一下

假设给出的三个点为\((1, 3)(2, 7)(3, 13)\)

直接把\(f(k)展开\)

\(f(k) = 3 \frac{(k - 2)(k - 3)}{(1 - 2)(1 - 3)} + 7\frac{(k-1)(k-2)}{(2 - 1)(2-3)} + 13\frac{(k-1)(k-2)}{(3 -1)(3-2)}\)

观察不难得到，如果我们把\(x_i\)带入的话，除第\(i\)项外的每一项的分子中都会有\(x_i - x_i\)，这样其他的所有项就都被消去了

因此拉格朗日插值法的正确性是可以保证的

下面说一下拉格朗日插值法的拓展

在\(x\)取值连续时的做法

在绝大多数题目中我们需要用到的\(x_i\)的取值都是连续的，这样的话我们可以把上面的算法优化到\(O(n)\)复杂度

首先把\(x_i\)换成\(i\)，新的式子为

\(f(k) = \sum_{i=0}^n y_i \prod_{i \not = j} \frac{k - j}{i - j}\)

考虑如何快速计算\(\prod_{i \not = j} \frac{k - j}{i - j}\)

对于分子来说，我们维护出关于\(k\)的前缀积和后缀积，也就是

\[pre_i = \prod_{j = 0}^{i} k - j
\]

\[suf_i = \prod_{j = i}^n k - j
\]

对于分母来说，观察发现这其实就是阶乘的形式，我们用\(fac[i]\)来表示\(i!\)

那么式子就变成了

\[f(k) = \sum_{i=0}^n y_i \frac{pre_{i-1} * suf_{i+1}}{fac[i] * fac[N - i]}
\]

注意:分母可能会出现符号问题，也就是说，当\(N - i\)为奇数时，分母应该取负号

重心拉格朗日插值法

再来看一下前面的式子

\[f(k) = \sum_{i = 0}^{n} y_i \prod_{i \not = j} \frac{k - x[j]}{x[i] - x[j]}
\]

设\(g = \prod_{i=0}^n k - x[i]\)

\[f(k) = g\sum_{i = 0}^{n} \prod_{i \not = j} \frac{y_i}{(k - x[i])(x[i] - x[j])}
\]

设\(t_i = \frac{y_i}{\prod_{j \not =i} x_i - x_j}\)

\[f(k) = g\sum_{i = 0}^{n} \frac{t_i}{(k - x[i])}
\]

这样每次新加入一个点的时候只需要计算它的\(t_i\)即可

应用

首先讲一个经典应用：计算\(\sum_{i=1}^n i^k (n \leqslant 10^{15}, k \leqslant 10^6)\)

老祖宗告诉我们，这个东西是个以\(n\)为自变量的\(k + 1\)次多项式，具体证明可以看第二份参考资料

然后直接带入\(k+1\)个点后用拉格朗日插值算即可，复杂度\(O(k)\)

那具体在题目中怎么使用拉格朗日插值呢？

首先你要证明求的东西是某个多项式，判断的依据是：



大部分情况下归纳一下就可以了

时间复杂度\(O(n^2)\)

int n,k,x[N],y[N];
int main(){
	read(n),read(k);
	for(int i=1;i<=n;++i) read(x[i]),read(y[i]);
	int ans=0;
	for(int i=1;i<=n;++i){
		int val=1;
		for(int j=1;j<=n;++j)if(j!=i) val=mul(val,add(x[i],mod-x[j]));
		val=mul(y[i],fpow(val,mod-2));
		for(int j=1;j<=n;++j)if(j!=i) val=mul(val,add(k,mod-x[j]));
		ans=add(ans,val);
	}
	printf("%d\n",ans);
	return 0;
}

成绩比较

有n个人m门学科，第i门的分数为不大于U_i的一个正整数

定义A「打爆」B当且仅当A的每门学科的分数都不低于B的该门学科的分数

已知第一个人第i们学科的排名为Ri，

即这门学科不低于n−R_i人的分数，但一定低于R_i−1人的分数

求有多少种方案使得第一个人恰好「打爆」了k个人

两种方案不同当且仅当存在两个人的分数不同

n,m≤100，U_i≤10⁹

梦的题解

首先容斥

设\(g_x\)表示第一个人至少「打爆」了\(x\)个人的方案数,

\(A_i\)表示给所有人第\(i\)门学科分配分数使得第一个人排名正确的方案数，有

\[g_x=\binom{n-1}{x} \prod\limits_{i=1}^m \binom{n-x-1}{n-x-R_i}A_i
\]

\[A_i=\sum\limits_{j=1}^{U_i}j^{n-R_i}(U_i-j)^{R_i-1}
\]

\(g_x\)的意义是：先选出被吊打的\(x\)个人，再枚举每一门学科，这门学科比\(n-R_i\)人高。除去被吊打的\(x\)人外还需要在未被吊打的\(n-x-1\)人中选出\(n-R_i-x\)人这门比第一个人低，然后再给这\(n\)个人分配分数。

\(A_i\)的意义是：枚举第一个人第\(i\)门的分数\(j\)，有\(n-R_i\)人分数不能高于\(j\),其余\(R_i-1\)人分数必须高于\(j\)。

容易发现瓶颈在快速计算$ A_i$上

我们将\(A_i\)二项式展开得

\[A_i=\sum\limits_{j=1}^{U_i}j^{n-R_i}(U_i-j)^{R_i-1}\\
=\sum\limits_{j=1}^{U_i}j^{n-R_i}\sum\limits_{k=0}^{R_i-1} \binom{R_i-1}{k}{(U_i)}^k(-j)^{R_i-k-1}\\
=\sum\limits_{k=0}^{R_i-1} \binom{R_i-1}{k}{(U_i)}^k\sum\limits_{j=1}^{U_i}j^{n-R_i}(-j)^{R_i-k-1}\\
=\sum\limits_{k=0}^{R_i-1} \binom{R_i-1}{k}{(U_i)}^k(-1)^{R_i-k-1}\sum\limits_{j=1}^{U_i}j^{n-k-1}
\]

前半部分非常好算，后半部分是一个自然数幂和，可以拉格朗日插值解决

拉格朗日插值过程中可以通过预处理前后缀的方式去掉不必要的求逆元复杂度使除预处理外单次\(O(n)\)。

这样就可以快速算出\(g_x\)了。

然后就是喜闻乐见的二项式反演环节

设\(f_x\)表示第一个人恰好「打爆」了$ x$个人

有

\[g_x=\sum\limits_{i=x}^n \binom{i}{x}f_i
\]

\[f_x=\sum\limits_{i=x}^n(-1)^{i-x} \binom{i}{x}g_i
\]

然后这道题就解决了，总复杂度：\(O(n^2m)\)

co int N=100+10;
int fac[N],ifac[N];
int sp[N][N]; // the sum of the ith power of 1~j

il int binom(int n,int m){
	return mul(fac[n],mul(ifac[m],ifac[n-m]));
}
int calc(int n,int k){
	if(!k) return n;
	if(n<N) return sp[k][n];

	static int pre[N],suf[N];
	pre[0]=1;
	for(int i=1;i<=k+2;++i) pre[i]=mul(pre[i-1],n-i);
	suf[k+3]=1;
	for(int i=k+2;i>=1;--i) suf[i]=mul(suf[i+1],n-i);

	int ans=0;
	for(int i=1;i<=k+2;++i){
		int down=mul(ifac[i-1],ifac[k+2-i]);
		if((k+2-i)&1) down=mod-down;
		ans=add(ans,mul(sp[k][i],mul(pre[i-1],mul(suf[i+1],down))));
	}
	return ans;
}

int U[N],R[N];
int A[N],g[N];
int main(){
	fac[0]=1;
	for(int i=1;i<N;++i) fac[i]=mul(fac[i-1],i);
	ifac[N-1]=fpow(fac[N-1],mod-2);
	for(int i=N-2;i>=0;--i) ifac[i]=mul(ifac[i+1],i+1);
	for(int i=1;i<N;++i)
		for(int j=1;j<N;++j) sp[i][j]=add(sp[i][j-1],fpow(j,i));

	int n=read<int>(),m=read<int>(),K=read<int>();
	for(int i=1;i<=m;++i) read(U[i]);
	for(int i=1;i<=m;++i) read(R[i]);

	for(int i=1;i<=m;++i)
		for(int k=0;k<=R[i]-1;++k){
			int sum=mul(binom(R[i]-1,k),mul(fpow(U[i],k),calc(U[i],n-k-1)));
			A[i]=add(A[i],(R[i]-k-1)&1?mod-sum:sum);
		}
	for(int i=1;i<n;++i){
		g[i]=binom(n-1,i);
		for(int j=1;j<=m;++j){
			if(n-i-R[j]<0) {g[i]=0;break;}
			g[i]=mul(g[i],mul(binom(n-i-1,n-i-R[j]),A[j]));
		}
	}

	int ans=0;
	for(int i=K;i<=n;++i){
		int sum=mul(binom(i,K),g[i]);
		ans=add(ans,(i-K)&1?mod-sum:sum);
	}
	printf("%d\n",ans);
	return 0;
}