由小学知识可知，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; }
