拉格朗日插值定理

拉格朗日插值学习

基本模型

• 定理模型： 已知 n+1 个点 x i x_i xi​ 及对应的 f ( x i ) f(x_i) f(xi​)，如果 f ( x ) f(x) f(x)是一个n次函数，拉格朗日插值可以唯一确定出 f ( x ) f(x) f(x)，并且 O ( n 2 ) O(n^2) O(n2) 求出 f ( k ) f(k) f(k) 。
• 直接结论： f ( x ) = ∑ i = 0 n f ( x i ) × ∏ j = 0 , j ! = i n x − x j x i − x j f(x)=\sum_{i=0}^nf(x_i)\times\prod_{j=0,j!=i}^n\frac{x-x_j}{x_i-x_j} f(x)=∑i=0n​f(xi​)×∏j=0,j!=in​xi​−xj​x−xj​​
• 简单证明： ∏ j = 0 , j ! = i n x − x j x i − x j \prod_{j=0,j!=i}^n\frac{x-x_j}{x_i-x_j} ∏j=0,j!=in​xi​−xj​x−xj​​有一个特点：当 x ≠ i x\not=i x​=i 时，为0；当 x = i x=i x=i 时，为 1。那么对于这 n + 1 n+1 n+1 个点 ( x i , f ( x i ) ) (x_i,f(x_i)) (xi​,f(xi​)) ，上式均成立。当 f ( x ) f(x) f(x) 为 n 次函数的时候，经过这 n+1 个点的函数只有唯一一个，那么就只能是上式。
• 时间复杂度： 对于一次查询 f ( k ) f(k) f(k) ，时间复杂度 O ( n 2 ) O(n^2) O(n2)

代码如下：小数版f(k)

int main(){
	double ans=0;
	for(int i=0;i<=n;i++){
		double t=y[i];
		for(int j=0;j<=n;j++){
			if(j!=i)t*=(k-x[j])/(x[i]-x[j]);
		}
		ans+=t;
	}
	cout<<ans;
}
           

代码如下：取模版f(k)%p

int main(){
	long long ans=0;
	for(int i=0;i<=n;i++){
		long long t1=y[i],t2=1;
		for(int j=0;j<=n;j++){
			if(j!=i){
				t1=t1*(k-x[j])%p;
				t2=t2*(x[i]-x[j])%p;
			}
		}
		ans=(ans+t1*ksm(t2,p-2)%p)%p;
	}
	cout<<(ans%p+p)%p;
}
           

特殊型：点连续

• 模型描述：当给定的 n n n 个点为 x i = i x_i=i xi​=i 时，原式变为 f ( x ) = ∑ i = 0 n f ( i ) × ∏ j = 0 , j ! = i n x − j i − j f(x)=\sum_{i=0}^nf(i)\times\prod_{j=0,j!=i}^n\frac{x-j}{i-j} f(x)=∑i=0n​f(i)×∏j=0,j!=in​i−jx−j​。其中前缀积 p r e i = ∏ j = 0 i ( x − j ) pre_i=\prod_{j=0}^i(x-j) prei​=∏j=0i​(x−j)；后缀积 s u f i = ∏ j = i n ( x − j ) suf_i=\prod_{j=i}^n(x-j) sufi​=∏j=in​(x−j)；阶乘 f a c i = i ! fac_i=i! faci​=i!。那么 f ( x ) = ∑ i = 0 n f ( i ) × p r e i − 1 × s u r i + 1 f a c i × f a c n − i × ( − 1 ) n − i f(x)=\sum_{i=0}^nf(i)\times \frac{pre_{i-1}\times sur_{i+1}}{fac_i\times fac_{n-i}}\times(-1)^{n-i} f(x)=∑i=0n​f(i)×faci​×facn−i​prei−1​×suri+1​​×(−1)n−i

一些小常识

• 1. n n n 次多项式的前 n 项和是 n+1 次多项式。

练习题

模板题

例题2

• 题目描述：给定n,k，求 ∑ i = 0 n i k \sum_{i=0}^ni^k ∑i=0n​ik mod 1000000007，其中1<=n<=1e18，k=1e5。
• 问题分析： ∑ i = 1 n i 1 \sum_{i=1}^ni^1 ∑i=1n​i1 为二次函数， ∑ i = 1 n i 2 \sum_{i=1}^n i^2 ∑i=1n​i2为三次函数， ∑ i = 1 n i 3 \sum_{i=1}^ni^3 ∑i=1n​i3 为四次函数，那么很容易猜想到 ∑ i = 1 n i k \sum_{i=1}^n i^k ∑i=1n​ik是一个 k+1 次函数。求出 ( x i , f ( x i ) ) (x_i,f(x_i)) (xi​,f(xi​)),0<=i<=k，带入拉格朗日插值公式即可求出 f ( x ) f(x) f(x)，并求出 f ( n ) f(n) f(n)。

例题3

• 题目描述：定义 f ( x ) f(x) f(x)是一个n次多项式，即 f ( x ) = a 0 x 0 + x 1 x 1 + x 2 x 2 + … … + x n x n f(x)=a_0x^0+x_1x^1+x_2x^2+……+x_nx^n f(x)=a0​x0+x1​x1+x2​x2+……+xn​xn。a_sing不知道任何一个 a i a_i ai​，但它知道 f ( 0 ) , f ( 1 ) , f ( 2 ) … … f ( n ) f(0),f(1),f(2)……f(n) f(0),f(1),f(2)……f(n)。有q个问题，每个问题查询 ∑ i = L R f ( i ) \sum_{i=L}^Rf(i) ∑i=LR​f(i) mod 9999991。其中1<=n<=1e4，q=1e3，0<=L<=R<=1e18。
• 问题分析：已知 n+1 个点 x i x_i xi​ 及对应的 f ( x i ) f(x_i) f(xi​)，拉格朗日可以直接求出 f ( x ) f(x) f(x)的通项。但是我们需要去求前缀和才能快速求上式，而L,R的值太大了，无法预处理。我们知道，一个n次函数的前k项和是n+1次函数，即 ∑ i = 0 k f ( i ) \sum_{i=0}^kf(i) ∑i=0k​f(i)是一个n+1次函数，我们只需要找到n+2个已知点就可拉格朗日插值求出该通项了。但是我们只知道n+1个点，我们可以先用拉格朗日插值求出第n+2个点即 f ( n + 1 ) f(n+1) f(n+1)。这样就有n+2个点的值了，再用拉格朗日插值即可求出 ∑ i = 0 k f ( i ) \sum_{i=0}^kf(i) ∑i=0k​f(i)的通项。