Archie

拉格朗日插值法

知道了n个点的坐标，构造出一个n次多项式

然后求f(x)

公式

$ fk=sum{i=1}^nyiprod{j=1quad jneq i }^nfrac{k-x_j}{x_i-x_j}$

就行了

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define ll long long
using namespace std;
int n,k;
ll mod=998244353;
ll x[20005];
ll y[20005];
ll power(ll x,ll y){
    ll ans=1;
    while(y){
        if(y&1){
            ans*=x;
            ans%=mod;
        }
    x*=x;
    y>>=1;
    x%=mod;
    }
    return ans;
}
int ans;
int main(){
    cin>>n>>k;
    for(int i=1;i<=n;++i){
        cin>>x[i]>>y[i];
    }
    for(int i=1;i<=n;++i){
        ll nx=y[i],ny=1;
        for(int j=1;j<=n;++j){
            if(i==j) continue;
            nx*=(k-x[j])%mod;nx%=mod;
            ny*=(x[i]-x[j])%mod;ny%=mod;
        }
        nx=nx*power(ny,mod-2)%mod;
        ans=(ans+nx)%mod;
    }
    cout<<(ans+mod)%mod;
    return 0;
}