嘟嘟嘟
本来以为拉格朗日插值是一个很复杂的东西，今天学了一下才知道就是一个公式……
我们都知道\(n\)个点\((x_i, y_i)\)可以确定唯一一个最高次为\(n - 1\)的多项式，那么现在我们已知这\(n\)个点，求这个多项式代入\(k\)时的值。
首先都能想到用高斯消元\(O(n ^3)\)求出多项式，然后代入\(k\)。
但是这样有点慢，于是拉格朗日就找到了一种\(O(n ^2)\)的方法。
他不知怎么的想出了这么一个式子：
\[f(k) = \sum_{i = 0} ^{n}{y_i} \prod_{i \neq j} \frac{k - x_j}{x_i - x_j}
\]
\]
然后就是\(O(n ^2)\)的啦。
至于正确性，我也不知道我这算不算证明，就是把\(k = x_t\)代入，会发现\(\sum\)中对于所有的\(i \neq x_t\)的项，都有一个\((x_t - x_t)\)。所以其他项消了。然后对于\(i = x_t\)的项，化简完后刚好等于\(y_t\)。
这题代码
#include<cstdio>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<cctype>
#include<vector>
#include<stack>
#include<queue>
using namespace std;
#define enter puts("")
#define space putchar(' ')
#define Mem(a, x) memset(a, x, sizeof(a))
#define In inline
typedef long long ll;
typedef double db;
const int INF = 0x3f3f3f3f;
const db eps = 1e-8;
const int maxn = 2e3 + 5;
const ll mod = 998244353;
inline ll read()
{
ll ans = 0;
char ch = getchar(), last = ' ';
while(!isdigit(ch)) last = ch, ch = getchar();
while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
if(last == '-') ans = -ans;
return ans;
}
inline void write(ll x)
{
if(x < 0) x = -x, putchar('-');
if(x >= 10) write(x / 10);
putchar(x % 10 + '0');
}
int n, k;
struct Node
{
int x, y;
}t[maxn];
In ll quickpow(ll a, ll b)
{
ll ret = 1;
for(; b; b >>= 1, a = a * a % mod)
if(b & 1) ret = ret * a % mod;
return ret;
}
In ll lagrange(int k)
{
ll ret = 0;
for(int i = 0; i < n; ++i)
{
ll sum1 = 1, sum2 = 1;
for(int j = 0; j < n; ++j) if(i ^ j)
{
sum1 = sum1 * (1LL * k - t[j].x + mod) % mod;
sum2 = sum2 * (t[i].x - t[j].x + mod) % mod;
}
ret = (ret + t[i].y * sum1 % mod * quickpow(sum2, mod - 2)) % mod;
}
return ret;
}
int main()
{
n = read(); k = read(); //n个点确定了一个n - 1次的多项式
for(int i = 0; i < n; ++i) t[i].x = read(), t[i].y = read();
write(lagrange(k)), enter;
return 0;
}