插值法(拉格朗日插值)讲解

拉格朗日插值区间误差限拉格朗日插值方法是一种常用的数值插值方法，用于在给定一组已知数据点的情况下，通过构造一个多项式函数来拟合这些数据点，并在插值区间内求得未知值。

然而，由于插值方法的近似性质，插值结果与真实值之间总会存在一定的误差。

本文将介绍拉格朗日插值法以及其误差限的计算方法。

一、拉格朗日插值法简介拉格朗日插值法是一种基于多项式的插值方法，其基本思想是通过构造一个满足给定数据点的插值多项式来逼近真实的函数曲线。

具体而言，对于给定的n个数据点(xi, yi)，拉格朗日插值法的插值多项式可以表示为：P(x) = Σ[ yi * Li(x) ]，i=0 to n其中，Li(x)是拉格朗日基函数，定义为：Li(x) = Π[ (x - xj) / (xi - xj) ]，j=0 to n，i ≠ j这样，通过求解插值多项式P(x)，我们可以在插值区间内求得未知值。

二、插值误差限的计算尽管拉格朗日插值法可以通过构造插值多项式来逼近真实函数曲线，但由于插值方法本质上是一种近似方法，插值结果与真实值之间总会存在一定的误差。

我们可以通过计算插值误差限来评估插值的可靠性。

在拉格朗日插值法中，插值误差限可通过以下等式进行估计：| f(x) - P(x) | ≤ M / (n + 1)! * | x - x0 | * | x - x1 | * ... * | x - xn |其中，f(x)是真实函数的值，P(x)是插值多项式的值，M是插值区间上函数f(x)的最大导数的上界，n是插值多项式的次数。

三、拉格朗日插值法的应用示例为了更好地理解拉格朗日插值法及其误差限的计算方法，我们来看一个具体的示例。

假设我们要通过拉格朗日插值法来估计函数f(x) = sin(x)在区间[0, π]内的某个未知值。

已知在该区间内取了n+1个等间距的数据点(xi, yi)，其中i=0, 1, 2, ..., n。

首先，我们可以根据已知数据点构造拉格朗日插值多项式P(x)，并计算出未知值的近似值。

【学习笔记】拉格朗⽇插值学习多项式的第⼀步。

参考资料：1.拉格朗⽇插值法的简介问题：解法1：⾼斯消元显然deg⩾n的多项式有⽆穷个，因为根据⾼斯消元，⼀定会出现⾃由元。

直接把这n个点列出⽅程组，⽤⾼斯消元求解。

求出多项式后再求出f(k)即可。

时间复杂度O(n3).解法2：拉格朗⽇插值法给出⼀个关于点(x i,y i)的基函数：g(k)=1⩽j⩽n∏j≠ik−x jx i−x j容易发现：∀j≠i,g(x j)=0.因为累乘中总有k=x j,使得k−x j=x j−x j=0,g(x j)=0.对于j=i,g(x j)=1.因为累乘中每⼀项均为x i−x jx i−x j=1,g(xj)=1.于是我们的多项式就可以表⽰为：f(k)=n∑i=1y i×1⩽j⩽n∏j≠ik−x jx i−x j这样∀(x i,y i),f(x i)=y i,也可以据此求出f(k).⼤概因为要求逆元，所以时间复杂度为O(n2+n log n)=O(n2). code:#include <bits/stdc++.h>#define ll long longusing namespace std;int n;const ll mod = 998244353;ll x[2011], y[2011], k, ans;ll ksm(ll s1, ll s2) {if(!s2) return 1;if(s2 & 1) return s1 * ksm(s1, s2 - 1) % mod;ll ret = ksm(s1, s2 / 2);return ret * ret % mod;}int main() {scanf("%d%lld", &n, &k);for(int i = 1; i <= n; i++) scanf("%lld%lld", &x[i], &y[i]);for(int i = 1; i <= n; i++) {ll sum = 1, mul = 1;for(int j = 1; j <= n; j++) {if(i == j) continue;sum *= (k - x[j]); sum %= mod; sum += mod; sum %= mod;mul *= (x[i] - x[j]); mul %= mod; mul += mod; mul %= mod;}sum *= ksm(mul, mod-2); sum %= mod;ans += (sum * y[i]) % mod; ans %= mod;}printf("%lld\n", ans);return 0;}2.拉格朗⽇插值法的拓展问题：同上，加⼊x i的值连续的限制。

拉格朗日插值法5.2 拉格朗日（Lagrange）插值可对插值函数选择多种不同的函数类型，由于代数多项式具有简单和一些良好的特性，例如，多项式是无穷光滑的，容易计算它的导数和积分，故常选用代数多项式作为插值函数。

5.2.1 线性插值问题5.1给定两个插值点其中，怎样做通过这两点的一次插值函数？过两点作一条直线，这条直线就是通过这两点的一次多项式插值函数，简称线性插值。

如图5.1所示。

图5.1 线性插值函数在初等数学中，可用两点式、点斜式或截距式构造通过两点的一条直线。

下面先用待定系数法构造插值直线。

设直线方程为，将分别代入直线方程得：当时，因，所以方程组有解，而且解是唯一的。

这也表明，平面上两个点，有且仅有一条直线通过。

用待定系数法构造插值多项式的方法简单直观，容易看到解的存在性和惟一性，但要解一个方程组才能得到插值函数的系数，因工作量较大和不便向高阶推广，故这种构造方法通常不宜采用。

当时，若用两点式表示这条直线，则有：（5.1）这种形式称为拉格朗日插值多项式。

，，称为插值基函数，计算，的值，易见（5.2）在拉格朗日插值多项式中可将看做两条直线，的叠加，并可看到两个插值点的作用和地位都是平等的。

拉格朗日插值多项式型式免除了解方程组的计算，易于向高次插值多项式型式推广。

线性插值误差定理5.1记为以为插值点的插值函数，。

这里，设一阶连续可导，在上存在，则对任意给定的，至少存在一点，使（5.3）证明令，因是的根，所以可设对任何一个固定的点，引进辅助函数：则。

由定义可得，这样至少有3个零点，不失一般性，假定，分别在和上应用洛尔定理，可知在每个区间至少存在一个零点，不妨记为和，即和，对在上应用洛尔定理，得到在上至少有一个零点，。

现在对求二次导数，其中的线性函数)，故有代入，得所以即5.2.2 二次插值问题5.2给定三个插值点，,其中互不相等，怎样构造函数的二次的（抛物线）插值多项式？平面上的三个点能确定一条次曲线，如图5.2所示。

常见的插值方法及其原理1. 拉格朗日插值法（Lagrange Interpolation）拉格朗日插值法是一种基于多项式的插值方法，通过n+1个已知点的函数值来构造一个n次多项式。

具体的计算公式如下：L(x) = Σ[yk * lk(x)], k=0 to n其中yk为已知点（xi, yi）的函数值，lk(x)为拉格朗日基函数，定义为：lk(x) = Π[(x - xj)/(xi - xj)], j=0 to n, j≠k拉格朗日插值法的原理是通过构造一个通过已知点的n次多项式，来代替未知函数的近似值。

利用拉格朗日基函数的性质，可以保证插值多项式通过已知点。

2. 牛顿插值法（Newton Interpolation）牛顿插值法是一种递推的插值方法，通过已知点的函数值和差商来逐步构造插值多项式。

差商的定义如下：f[x0]=y0f[x1]=(f[x1]-f[x0])/(x1-x0)f[x2]=(f[x2]-f[x1])/(x2-x1)...f[xn] = (f[xn] - f[xn-1]) / (xn - xn-1)利用差商的定义，可以得到牛顿插值多项式的表达式：N(x) = f[x0] + f[x0, x1](x-x0) + f[x0, x1, x2](x-x0)(x-x1) + ... + f[x0, x1, ..., xn](x-x0)(x-x1)...(x-xn)牛顿插值法的原理是通过递推计算差商来得到插值多项式。

通过使用差商来处理已知点的函数值差异，可以得到更高次的插值多项式。

3. 样条插值法（Spline Interpolation）样条插值法是一种基于分段低次插值函数的插值方法，常用的是三次样条插值。

样条插值法通过寻找一组分段函数，使得满足原函数的插值条件，并要求函数在每个插值点处的函数值、一阶导数和二阶导数连续。

这样可以保证插值函数在每个插值点处的平滑性。

三次样条插值法的原理是将整个插值区间划分为多个小区间，在每个小区间内使用三次多项式进行插值。

excel拉格朗日插值函数Excel拉格朗日插值函数是一种常用的数据插值方法，在很多领域都有应用，比如工程建模、生物信息学、金融分析等。

本文将从介绍插值方法的基本原理、数学公式和Excel计算方法方面进行讲解，希望使读者能够更好地掌握Excel拉格朗日插值函数的使用方法。

一、插值方法的基本原理插值方法是一种基于已知数据点推导出未知数据点值的数学方法。

在实际应用过程中，很多情况下我们只知道若干个数据点的取值，但是我们需要获得数据点之间的中间值或者在这些数据点之外的其他值。

这时候，插值方法就可以发挥作用。

插值方法的基本思路是，利用已知点之间的最高次多项式函数将数据点连接起来，然后求出函数在某个未知点的取值。

一般来说，如果已知数据点越多，则插值计算得到的结果越准确。

在拉格朗日插值方法中，我们使用拉格朗日多项式来计算未知点的取值。

拉格朗日多项式的原理是，将已知点看作多个线性项的积，然后通过一系列复杂的运算，得到一个关于自变量x的多项式函数。

二、拉格朗日插值法的数学公式假设我们有n个数据点{(x1,y1),(x2,y2),...(xn,yn)}，其中x1<x2<...<xn。

我们需要在这些数据点之间插值计算出某个未知点x的函数值y。

y = Σ(yi * Li(x))i从1到n，Li(x)为拉格朗日多项式（Lagrange polynomial），表达式为：Li(x) = Π(j ≠ i)((x - xj)/(xi - xj))j从1到n。

三、Excel计算方法Excel中可以使用插值函数进行插值计算。

要使用拉格朗日插值函数，可以先使用X轴和Y轴的数据点构建一个散点图，然后使用趋势线功能来生成拉格朗日插值函数的公式。

1. 创建散点图在Excel中选中所需要插值的数据点，然后点击插入菜单中的散点图选项。

这时候，Excel将在新的工作表中创建一个散点图，并根据数据点自动添加X轴和Y轴的标签。

2. 添加趋势线在散点图中，我们需要生成一条趋势线来表示拉格朗日插值函数。

拉格朗日插值法牛顿插值法
摘要：
1.插值法的概念和作用
2.拉格朗日插值法原理和应用
3.牛顿插值法原理和应用
4.两种插值法的优缺点比较
正文：
一、插值法的概念和作用
插值法是一种数学方法，通过已知的数据点来预测未知数据点的一种技术。

在科学计算和工程应用中，常常需要根据有限个已知数据点，来估计某个函数在其他点上的值。

插值法正是为了解决这个问题而诞生的。

二、拉格朗日插值法原理和应用
拉格朗日插值法是一种基于拉格朗日基函数的插值方法。

它的基本原理是：在给定的区间[a, b] 上，选取一个基函数，然后通过求解一组线性方程，得到基函数在各数据点上的值，最后用这些值来近似函数在待求点上的值。

拉格朗日插值法广泛应用于数值分析、工程计算等领域。

三、牛顿插值法原理和应用
牛顿插值法，又称为牛顿前向差分法，是一种基于差分的插值方法。

它的基本原理是：通过对已知数据点的函数值进行差分，然后使用牛顿迭代公式来求解差分后的函数在待求点上的值。

牛顿插值法具有较高的精度，适用于各种函数，特别是对于单调函数和多项式函数，效果尤为显著。

四、两种插值法的优缺点比较
拉格朗日插值法和牛顿插值法各有优缺点。

拉格朗日插值法的优点是适用范围广，可以插值任意类型的函数，但计算过程较为复杂；牛顿插值法的优点是计算简便，精度高，但对于非线性函数或多峰函数，效果可能不佳。

因此，在实际应用中，需要根据具体情况选择合适的插值方法。

拉格朗日插值法的一些讨论学院： 班级： 姓名： 学号: 引言——在数值分析中，拉格朗日插值法是以法国十八世纪数学家约瑟夫·路易斯·拉格朗日命名的一种多项式插值方法。

许多实际问题中都用函数来表示某种内在联系或规律，而不少函数都只能通过实验和观测来了解。

如对实践中的某个物理量进行观测，在若干个不同的地方得到相应的观测值，拉格朗日插值法可以找到一个多项式，其恰好在各个观测的点取到观测到的值。

这样的多项式称为拉格朗日（插值）多项式。

数学上来说，拉格朗日插值法可以给出一个恰好穿过二维平面上若干个已知点的多项式函数。

拉格朗日插值法最早被英国数学家爱德华·华林于1779年发现，不久后（1783年）由莱昂哈德·欧拉再次发现。

1795年，拉格朗日在其著作《师范学校数学基础教程》中发表了这个插值方法，从此他的名字就和这个方法联系在一起。

数据建模有两大方法：一类是插值方法，另一类是拟合函数一般的说，插值法比较适合数据准确或数据量小的情形。

然而Lagrange 插值有很多种，1阶，2阶,…n 阶。

我们可以利用拉格朗日插值求方程，根据它的程序求原方程的图像。

下面我具体介绍分析一下拉格朗日插值的算法设计及应用。

具体算法1、基本概念已知函数y=f(x)在若干点i x 的函数值i y =()i x f （i=0,1,⋅⋅⋅,n ）一个差值问题就是求一“简单”的函数p(x)：p(i x )=i y ,i=0,1,⋅⋅⋅,n,(1)则p(x)为f(x)的插值函数，而f(x)为被插值函数会插值原函数，0x ，1x ，2x ，...,n x 为插值节点，式（1）为插值条件，如果对固定点-x 求f(-x )数值解，我们称-x 为一个插值节点，f(-x )≈p(-x )称为-x 点的插值，当-x ∈[min(0x ，1x ，2x ，...,n x )，max(0x ，1x ，2x ，...,n x )]时，称为内插，否则称为外插式外推，特别地，当p(x)为不超过n 次多项式时称为n 阶Lagrange 插值。

拉格朗日插值公式和牛顿插值公式拉格朗日插值公式和牛顿插值公式是数值分析中常用的插值方法，用于通过已知数据点推导出未知数据点的近似值。

本文将分别介绍这两个插值方法的原理和应用，并比较它们的特点和优劣。

一、拉格朗日插值公式拉格朗日插值公式是由法国数学家拉格朗日于18世纪提出的，它通过构造一个多项式来逼近给定的数据点集合。

具体而言，拉格朗日插值多项式的形式为：P(x) = Σ(yi * Li(x))其中，P(x)表示待求的多项式，yi表示已知数据点的函数值，Li(x)称为拉格朗日基函数，它代表了每个数据点的贡献度。

拉格朗日插值公式的优点在于其简单易懂，计算过程相对简单快速。

但是，该方法的缺点是对于较大规模的数据集合，计算量会变得很大，同时当数据点之间的间距不均匀时，插值结果可能出现较大误差。

二、牛顿插值公式牛顿插值公式是由英国数学家牛顿于17世纪提出的，它采用了多项式的差商形式进行插值。

具体而言，牛顿插值多项式的形式为：P(x) = f[x0] + (x - x0)f[x0, x1] + (x - x0)(x - x1)f[x0, x1,x2] + ...其中，f[x0]表示已知数据点的函数值，f[x0, x1]表示x0和x1两个点之间的差商，以此类推。

牛顿插值公式的优点在于可以通过递推的方式计算差商，避免了重复计算，因此对于较大规模的数据集合，计算效率较高。

此外，牛顿插值公式对于不均匀间距的数据点也能够较好地逼近。

然而，牛顿插值公式的缺点在于其计算过程较为繁琐，需要额外计算差商。

三、比较与应用拉格朗日插值公式和牛顿插值公式都是常见的插值方法，它们在实际应用中各有优劣。

下面将对它们进行比较和应用分析。

1. 计算复杂度从计算复杂度的角度来看，牛顿插值公式在计算差商时需要递推计算，每次计算需要O(n)的复杂度，因此总的计算复杂度为O(n^2)。

而拉格朗日插值公式直接计算每个基函数，每次计算都需要O(n)的复杂度，因此总的计算复杂度也为O(n^2)。

重心拉格朗日插值法
摘要：
1.拉格朗日插值法的概念
2.拉格朗日插值法的基本原理
3.拉格朗日插值法的应用实例
4.拉格朗日插值法的优缺点
正文：
拉格朗日插值法是一种数学上的插值方法，其概念源于18 世纪意大利数学家拉格朗日提出的一种用于估算函数值的技巧。

拉格朗日插值法通过构造一组基函数，利用这些基函数的线性组合来逼近目标函数，从而达到插值的目的。

拉格朗日插值法的基本原理可以概括为：首先选择一组插值节点，然后根据插值节点构造基函数，接着用基函数的线性组合来表示目标函数，最后通过求解线性方程组得到目标函数在任意点的值。

拉格朗日插值法在实际应用中有很多实例，例如在数值分析中，可以用拉格朗日插值法求解微分方程的数值解；在工程领域，可以用拉格朗日插值法对非线性函数进行拟合，从而优化设计方案。

拉格朗日插值法具有一些优点，例如具有较高的插值精度，可以很好地逼近大多数函数；同时，拉格朗日插值法具有较好的稳定性，不容易出现震荡现象。

然而，拉格朗日插值法也存在一些缺点，例如计算过程中需要求解线性方程组，当插值节点较多时，计算量会显著增加，从而降低计算效率。

总之，拉格朗日插值法是一种实用的数学方法，广泛应用于各个领域。

拉格朗日插值法5.2 拉格朗日（Lagrange）插值可对插值函数选择多种不同的函数类型，由于代数多项式具有简单和一些良好的特性，例如，多项式是无穷光滑的，容易计算它的导数和积分，故常选用代数多项式作为插值函数。

5.2.1 线性插值问题5.1给定两个插值点其中，怎样做通过这两点的一次插值函数？过两点作一条直线，这条直线就是通过这两点的一次多项式插值函数，简称线性插值。

如图5.1所示。

图5.1 线性插值函数在初等数学中，可用两点式、点斜式或截距式构造通过两点的一条直线。

下面先用待定系数法构造插值直线。

设直线方程为，将分别代入直线方程得：当时，因，所以方程组有解，而且解是唯一的。

这也表明，平面上两个点，有且仅有一条直线通过。

用待定系数法构造插值多项式的方法简单直观，容易看到解的存在性和惟一性，但要解一个方程组才能得到插值函数的系数，因工作量较大和不便向高阶推广，故这种构造方法通常不宜采用。

当时，若用两点式表示这条直线，则有：（5.1）这种形式称为拉格朗日插值多项式。

，，称为插值基函数，计算，的值，易见（5.2）在拉格朗日插值多项式中可将看做两条直线，的叠加，并可看到两个插值点的作用和地位都是平等的。

拉格朗日插值多项式型式免除了解方程组的计算，易于向高次插值多项式型式推广。

线性插值误差定理5.1记为以为插值点的插值函数，。

这里，设一阶连续可导，在上存在，则对任意给定的，至少存在一点，使（5.3）证明令，因是的根，所以可设对任何一个固定的点，引进辅助函数：则。

由定义可得，这样至少有3个零点，不失一般性，假定，分别在和上应用洛尔定理，可知在每个区间至少存在一个零点，不妨记为和，即和，对在上应用洛尔定理，得到在上至少有一个零点，。

现在对求二次导数，其中的线性函数)，故有代入，得所以即5.2.2 二次插值问题5.2给定三个插值点，,其中互不相等，怎样构造函数的二次的（抛物线）插值多项式？平面上的三个点能确定一条次曲线，如图5.2所示。

浅谈拉格朗⽇插值浅谈拉格朗⽇插值在中，拉格朗⽇插值法是以法国⼗⼋世纪数学家命名的⼀种⽅法。

许多实际问题中都⽤函数来表⽰某种内在联系或规律，⽽不少函数都只能通过实验和观测来了解。

拉格朗⽇插值法可以找到⼀个，其恰好在各个观测的点取到观测到的值。

这样的多项式称为拉格朗⽇（插值）多项式。

——百度百科通俗地说，拉格朗⽇插值法可以找出⼀个恰好经过直⾓坐标系内n个给定点的函数众所周知，n个点能唯⼀确定的多项式最⾼次数是n−1次这个可以两点确定⼀次函数，三点确定⼆次函数来推出，或者我们由⽅程组有唯⼀解的充要条件也能得出知道了这个之后我们就容易想到直接⽤⾼斯消元来搞出多项式的系数，但是复杂度消耗太⼤，是O(n3)⽽拉格朗⽇插值法就是⼀种⼀般可以在O(n2)的复杂度下求出多项式的⽅法（不过通常⽤来求⼀个点值，以下的讲述⼀般以此为参考）⼀般的拉格朗⽇插值法我们设要求的多项式为f(x)，点的坐标为(x i,y i)，我们要找多项式在x0处的取值先上公式，由拉格朗⽇插值法：f(x0)=n∑i=1y i∏i≠jx0−x jx i−x j看起来不是很好理解，其实很简单，我们把原来的某个给定点x k代⼊以下有：f(x k)=n∑i=1y i∏i≠jx k−x jx i−x j容易发现，当k≠i时，后⾯的x k−x jx i−x j的分⼦总有⼀项是0，此时∏i≠jx k−x jx i−x j=0当k=i时，后⾯的x k−x jx i−x j上下完全相同，此时∏i≠jx k−x jx i−x j=1即对于f(x k)来说，这个多项式的确给出了对应的y k的值不难发现这个⽅法对所有点都适⽤，因此它是正确的从上⾯的式⼦可以看出每次计算要枚举两次，因此复杂度很简单，就是O(n2)在x取值连续时的插值法因为很多时候我们做题都是先发现某个函数是多少次的多项式，然后⾃⼰随意取⼀些值代⼊插值这样的话为了省事横坐标的取值完全可以从1开始连续取，那么我们把上⾯的式⼦中的x i换成i就有：f(x0)=n∑i=1y i∏i≠jx0−ji−j考虑怎么快速求∏i≠j k−ji−j，我们分别考虑：分⼦的话容易发现就是∏n t=1x0−t x0−i分母⽐较复杂，i−j的累乘可以分成两个阶乘部分，因此推导⼀下就是(−1)n−i⋅i!⋅(n−i)!这样我们⼀般就可以O(n log n)来算了（log主要是有求逆元的过程，当然你预处理O(n)求也没有问题）重⼼拉格朗⽇插值法我们考虑到朴素的拉格朗⽇插值每次多加⼊⼀个点时就要整个重新算过，很浪费时间那么能不能把重复算的⼀些东西利⽤起来？我们对于f(x0)=n∑i=1y i∏i≠jx0−x jx i−x j把分⼦提取出来，设为g=∏n i=1x0−x i，则此时：Processing math: 100%f(x0)=g⋅n∑i=1∏i≠jy i(x0−x i)(x i−x j)设⼀个t i=y i∏i≠j x i−x j，则：f(x0)=g⋅n∑i=1t ix0−x i因此每次多加⼊⼀个点只需要重新O(n)算它的t i就好了拉格朗⽇插值的应⽤以及常⽤解题思路⼀个经典例⼦：⾃然数幂和，即求∑n i=1i k之前也提到过⽤第⼆类斯特林数做的⽅法，但那种⽅法是O(k2)的，不够优秀但是现在我们观察这个式⼦，如果不看求和的话i k就是⼀个k次多项式那么前缀和（其实就是差分）之后，次数要+1，即此时答案为⼀个关于n的k+1多项式那我们直接代⼊k个值（取值连续，反正⾃⼰定）之后插值算即可，复杂度O(k log k)那么很多具体题⽬怎么办呢，⼀般就是先推出某个式⼦，然后证明它是关于某个⾃变量的多少次函数（⼀定要判断出次数！），然后⾃⼰选⼀些点（⼀般是连续的）代⼊插值即可其实做了⼀些题⽬之后就很套路了拉格朗⽇插值的模板模板看 ，就是⽤⼀般的O(n2)来做就好了CODE#include<cstdio>#define RI register int#define CI const int&using namespace std;const int N=2005,mod=998244353;int n,x[N],y[N],k;inline int sub(CI x,CI y){int t=x-y; return t<0?t+mod:t;}inline int inv(int x,int p=mod-2,int mul=1){for (;p;p>>=1,x=1LL*x*x%mod) if (p&1) mul=1LL*mul*x%mod; return mul;}inline int Lagrange(CI n,int *x,int *y,CI k){int ret=0; for (RI i=1;i<=n;++i){int s1=1,s2=1; for (RI j=1;j<=n;++j) if (i!=j)s1=1LL*s1*sub(k,x[j])%mod,s2=1LL*s2*sub(x[i],x[j])%mod;(ret+=1LL*y[i]*s1%mod*inv(s2)%mod)%=mod;}return ret;}int main(){scanf("%d%d",&n,&k); for (RI i=1;i<=n;++i) scanf("%d%d",&x[i],&y[i]);return printf("%d",Lagrange(n,x,y,k)),0;}⼀些⼊门例题提到过的⾃然数幂和需要容斥+组合数学+⼴义容斥化式⼦的⾃然数幂和DP+多项式差分系数推导之后⽤拉格朗⽇插值算答案。

拉格朗⽇插值法（图⽂详解）拉格朗⽇插值⼊门由⼩学知识可知，n个点(x_i,y_i)可以唯⼀地确定⼀个多项式现在，给定n个点，请你确定这个多项式，并将k代⼊求值求出的值对998244353取模Input第⼀⾏两个正整数n,k，含义如题接下来n⾏，每⾏两个正整数x_i,y_i含义如题。

n≤2000,xi,yi,k≤998244353Output⼀个整数表⽰答案Sample Input3 1001 42 93 16Sample Output10201//样例⼀中的三个点确定的多项式是f(x)=x^2+2x+1，将100代⼊求值得到10201int re=1;while(y){if(y&1) re=(x*re)%mod;x=(x*x)%mod;y>>=1;}return re;}int read(){int x=0,f=1;char ch=getchar();while(!isdigit(ch)){if(ch=='-')f=-f;ch=getchar();}while(isdigit(ch)){x=x*10+ch-48;ch=getchar();}return x*f;}signed main(){n=read(),k=read();for(int i=1;i<=n;i++)a[i]=read(),b[i]=read();for(int i=1;i<=n;i++){int tmp=1;for(int j=1;j<=n;j++)if(i!=j)tmp=tmp*(a[i]+mod-a[j])%mod; //分母tmp=quickpow(tmp,mod-2);for(int j=1;j<=n;j++)if(i!=j) tmp=tmp*(k+mod-a[j])%mod; //分⼦tmp=tmp*b[i]%mod;ans=(ans+tmp)%mod;}printf("%lld\n",ans);return 0;}#include<bits/stdc++.h>using namespace std;const int mod=998244353;int x[2010],y[2010],a=1,b=0;int powmod(int a,int b){int ans=1;while(b){if(b&1)ans=1ll*ans*a%mod;a=1ll*a*a%mod;b>>=1;}return ans;}int main(){int n,k;scanf("%d%d",&n,&k);for(int i=1;i<=n;i++)scanf("%d%d",x+i,y+i);for(int i=1;i<=n;i++){int a1=1,b1=1;//a1代表分母，b1代表分⼦b1=1ll*b1*y[i]%mod;for(int j=1;j<=n;j++)if(j!=i){b1=1ll*b1*(k-x[j])%mod;a1=1ll*a1*(x[i]-x[j])%mod;}b=(1ll*a1*b+1ll*a*b1)%mod;a=1ll*a*a1%mod;//b/a+b1/a1=(b*a1+a*b1)/(a*a1)}a=(a+mod)%mod,b=(b+mod)%mod;printf("%lld\n",1ll*b*powmod(a,mod-2)%mod);//因为带了除法，所以分母会⽐较⼤，于是在前⾯边乘边取模，最后取逆元return 0;}参考资料。

拉格朗日插值法原理：
拉格朗日插值法是一种多项式插值方法。

拉格朗日插值法是离散数学中进行曲线拟合的基本方法（即在工程实际中，我们所得到的结果往往是离散的点，而若想把这些离散的结果作为先验条件得到其他点就需要进行多项式拟合）。

其主要思想如下：
能找到一条曲线记为f，使其能穿过其中一个离散点(f(xa)=ya)并在其他离散点上的值为0（f(xb)=0）,则我们如果能找到每一点对应的曲线f,将其相加就可以得到一个能经过所有离散点的曲线F，我们认为F则为这些离散点的拟合多项式。

运用拉格朗日插值法需要注意：
1.拉格朗日插值法其找到的曲线是经过所有离散点的，因此对于偏离值无法进行剔除，很容易出现过拟合的现象，因此在实际工程应用中需要剔除偏移量。

2.拉格朗日插值法拟合n阶多项式至少需要n+1个点（公式推一下就可以知道，这里不在详述）
3.随阶数的增大拉普拉斯拟合法的时间复杂度成指数递增，我们不是数学家，不需要对原理进行优化，我的建议是试试异构（GPU+CPU混合编程会简单很多）。