由小学知识可知,n个点(xi,yi)可以唯一地确定一个多项式
现在,给定n个点,请你确定这个多项式,并将k代入求值
求出的值对998244353取模
#include <bits/stdc++.h>
using namespace std;
const int maxn = 1e5 + 5;
typedef long long ll;
const ll mod = 998244353;
ll xx[maxn], yy[maxn];
ll qpow(ll a, ll b) {
ll ans = 1;
while (b) {
if (b & 1) {
ans = (ans * a) % mod;
}
b >>= 1;
a = (a * a) % mod;
}
return ans % mod;
}
int main() {
ll n, k;
cin >> n >> k;
for (int i = 1; i <= n; i++) {
cin >> xx[i] >> yy[i];
}
ll ans = 0;
for (int i = 1; i <= n; i++) {
ll ret = 1, res = 1;
for (int j = 1; j <= n; j++) {
if (i == j)continue;
ret *= (k - xx[j]);
res *= (xx[i] - xx[j]);
ret = (ret % mod + mod) % mod;
res = (res % mod + mod) % mod;
}
ll tmp = qpow(res, mod - 2);
ans += yy[i] * tmp % mod * ret % mod;
ans %= mod;
}
cout << ans << endl;
return 0;
}