介绍

根据相关知识，我们知道：

n+1

个点能够确定一个

n

次的多项式函数。举个简单的例子，在初中阶段我们知道利用

2

个点可以确定一个一次函数解析式（其实就是两点确定一条直线），

3

个点能够确定一个二次函数解析式。

对于一个一次函数，我们有如下几种式子可以刻画：

一般式

Ax+By+C=0

点斜式

y=kx+b

截距式

\frac{x}{a}+\frac{y}{b}=1

不知道什么式（假设直线上两点为

(x_1,y_1)

，

(x_2,y_2)

）

y=y_1\frac{x-x_2}{x_1-x_2}+y_2\frac{x-x_1}{x_2-x_1}

最后这个式子为什么是正确的？因为我们把两点的横坐标带入可以得到纵坐标，又因为这个式子是一次的，所以上式成立。（如果你注意力足够强大就会发现其实这个式子和上面的截距式很相似。）

注意到这最后的式子只是和所有“点”相关的，不关系到其他的性质（比如一次函数是直线，而点斜式就是利用了直线斜率，截距式也是因为有直线才能通过“与坐标轴的截距”这样的方式刻画），就非常适合拓展。

比如说到了二次函数上：

一般式

y=ax^2+bx+c

顶点式

y=a(x-h)^2+k

交点式

y=a(x-x_1)(x-x_2)

依然不知道什么式

y=y_1\frac{(x-x_2)(x-x_3)}{(x_1-x_2)(x_1-x_3)}+y_2\frac{(x-x_1)(x-x_3)}{(x_2-x_1)(x_2-x_3)}+y_3\frac{(x-x_1)(x-x_2)}{(x_3-x_1)(x_3-x_2)}

发现好像只有一般式与这个式子能够继续拓展下去。

经过一番思考，我们好像发现

n

次多项式的表示方法：

\sum_{i=0}^na_ix^i \Leftrightarrow \sum_{i=1}^{n}(y_i\prod_{1\le j \le n,j \neq i}\frac{x-x_j}{x_i-x_j})

此时，如果我们给定

f(x)

的

n+1

个节点，要求一个

f(k)

的值，我们可以直接带入右边的式子。

代码

CPP

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<vector>
#include<queue>
#include<cstring>
#include<stack>
#include<map>
#include<algorithm>
#include<cmath>
#include<fstream>
#if __cplusplus >= 201103L
#include<random>
#include<unordered_map>
#endif
using namespace std;

#define endl '\n'
#define fi first
#define se second
#define _fil(__in,__out) freopen(__in,"r",stdin),freopen(__out,"w",stdout)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const int N=2e3+10;

inline ll fast(ll a,ll p,ll MD){ll ans=1;while(p){if(p&1)ans*=a,ans%=MD;a*=a;a%=MD;p>>=1;}return ans;}
ll x[N],y[N];
int main(){
    int n,k;cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>x[i]>>y[i];
    ll ans=0,MD=998244353;
    for(int i=1;i<=n;i++){
        ll nw=y[i];
        for(int j=1;j<=n;j++){
            if(j==i)continue;
            nw*=(k-x[j]);nw%=MD;
            nw*=fast(x[i]-x[j],MD-2,MD);nw%=MD;
        }
        // cout<<nw<<endl;
        ans+=nw;ans+=MD;ans%=MD;
    }
    cout<<ans<<endl;
}

拉格朗日插值法

文章操作

介绍

代码

相关推荐

评论

拉格朗日插值法