浅谈拉格朗日插值法
好像FFT要用到，所以就学习一手
版题
什么是插值
在离散数据的基础上补插连续的函数，使得这条连续函数经过所有离散数据点，这个过程就叫插值。
其意义在于：
插值是离散函数逼近的重要方法，利用它可通过函数在有限个点处的取值状况，估算出函数在其他点处的近似值。
就是把一个足球踢出去，假设球始终在一个平面上飞行，它的轨迹就可以抽象为 \(f(x\ （假设这个函数至于时间有关）
插值有许多方法，包括：三角函数插值；线性插值法；牛顿插值法；拉格朗日插值法 …… 但是蒟蒻只会拉格朗日插值法
拉格朗日插值法
举个例子，现在平面上有三个点分别是\((x_1 , y_1,(x_2 , y_2,(x_3 , y_3(x_1 < x_2 < x_3\，我们用这三个插值。
我们需要构造 \(n\ （这里是3）个函数。第 \(i\ 个函数满足：
\(
\left\{\begin{matrix}{aligned}
0 , x = x_j (j != i \\
1 , x = x_i \\
others , I \ don't \ care
\end{matrix}\right.
\
\[f_1 = \dfrac{(x - x_2(x - x_3}{(x_1 - x_2(x_1 - x_3}
\]
进一步推广：
\[f_i(x = \prod_{j \neq i} ^ {n}\dfrac{x - x^j}{x_i - x_j}
\]
\[f(x = \sum_{i = 1}^{n}y_i*f_i(x
\]
code
#include <bits/stdc++.h>
#define fu(x , y , z for(int x = y ; x <= z ; x ++
#define LL long long
using namespace std;
const LL mod = 998244353;
LL n , k;
struct RE {
LL x , y;
}re[2005];
LL read ( {
LL val = 0 , fu = 1;
char ch = getchar (;
while (ch < '0' || ch > '9' {
if (ch == '-' fu = -1;
ch = getchar (;
}
while (ch >= '0' && ch <= '9' {
val = val * 10 + (ch - '0';
ch = getchar (;
}
return val * fu;
}
LL ksm (LL x , LL y {
LL ans = 1;
while(y {
if(y&1 ans = ans * x %mod;
x = x * x % mod;
y >>= 1;
}
return ans;
}
int main ( {
LL ans = 0 , ans1;
n = read ( , k = read (;
fu (i , 1 , n {
re[i].x = read ( , re[i].y = read (;
}
fu (i , 1 , n {
ans1 = re[i].y;
fu (j , 1 , n
if (i ^ j
ans1 = 1ll * (ans1 * (k - re[j].x % mod * ksm (re[i].x - re[j].x , mod - 2 % mod;
ans = (ans + ans1+mod % mod;
}
printf ("%lld" , ans;
return 0;
}