拉格朗日插值公式

任给定\(F\)中\(2n+2\)个数\(x_1，x_2，…，x_{n+1}，y_1，y_2，…，y_{n+1}，\)其中\(x_1，x_2，…x_{n+1}\)互不相同，则存在唯一的次数不超过n的多项式\(f(x)\)，满足\(f(x_i)=y_i{\color{white}..}(i=1，2，…，n+1)\)，这里

\[f(x)=\sum_{i=1}^{n}{y_i\cdot\prod_{j\ne i}^{1\le j\le n}\frac{(x-x_j)}{(x_i-x_j)}}
\]

叫做拉格朗日插值公式。

公式的几何解释是：存在唯一的次数不超过\(n\)的抛物线

\[{\color{white}..} y=a_0+a_1 \cdot x+a_2 \cdot x^2+…+a_n \cdot a^n {\color{white}..}
\]

通过平面上的给出的\(n+1\)个点\(M_1(x_1，y_1)，M_2(x_2，y_2)，…，M_{n+1}(x_{n+1}，y_{n+1})\)。

特别地，如对于自变数的两个值，给出了线性函数的\((n=1)\)对应值，这线性函数就被确定。从几何方面说，直线由其两点确定，即：

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

code

给定 \(n\) 个点，确定这个 \(n-1\) 次多项式，并求出 \(f(k) \mod 998244353\) 的值。

AC·code


#include<bits/stdc++.h>
#define il inline
#define cs const
#define ri register
#define int long long 
using namespace std;
namespace Q{
    il int rd(){
        ri int x=0,f=1;ri char c=getchar();
        while(c<'0'||c>'9') f=(c=='-')?-1:1,c=getchar();
        while(c>='0'&&c<='9') x=x*10+(c^48),c=getchar();
        return x*f; 
    }
    il void wt(int x){
        if(x<0) x=-x,putchar('-');
        if(x>=10) wt(x/10);
        return putchar(x%10+48),void();
    }
}
cs int mod=998244353,N=2e3+5;
int n,k,x[N],y[N];
il int qpow(int a,int b){
    int as=1;
    while(b){
        if(b&1) as=as*a%mod;
        a=a*a%mod,b>>=1;
    }
    return as;
}
signed main(){
    n=Q::rd(),k=Q::rd();
    for(ri int i=1;i<=n;++i){
        x[i]=Q::rd(),y[i]=Q::rd();
    }
    int as=0;
    for(ri int i=1;i<=n;++i){
        int s=1;
        for(ri int j=1;j<=n;++j){
            if(i==j) continue;
            s=s*(k-x[j])%mod*qpow(x[i]-x[j],mod-2)%mod;
        }
        as=(as+s*y[i]%mod)%mod;
    }
    Q::wt((as%mod+mod)%mod);//!!!!!!!
    return 0;
}

原文链接: https://www.cnblogs.com/windymoon/p/17071094.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处：https://www.ccppcoding.com/archives/314439

非原创文章文中已经注明原地址，如有侵权，联系删除

关注公众号【高性能架构探索】，第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处！

拉格朗日插值

拉格朗日插值公式

code

相关推荐