~~水题解水题解~~
发现在许多题里面的拉插需要求系数，但这个题只求第 $k$ 项，就比较无能。于是来写一个求系数的题解。
~~好了别喷了我知道我把这题做成了一道模拟题~~
大概就是考虑拉格朗日插值的formula：
$$f=\sum y_i\prod_{i\not=j}\frac{x-x_j}{x_i-x_j}$$
然后根据这个模拟多项式运算即可。其中需要注意的是多项式除法，在除一个类似 $(x+t)$ 的式子的时候，用到的是大除法(即手算多项式除法)的方式进行，也不是很难推，模拟一下就好了。
```cpp
#include <bits/stdc++.h>
using namespace std ;
typedef long long ll ;
const int N = 1000010 ;
const int P = 998244353 ;
int n, k ;
void debug(int *tp, int minn, int maxn, char c){
for (int i = minn ; i <= maxn ; ++ i)
cout << tp[i] << " " ; cout << c ;
}
namespace Interpolation{
int ans ;
int now ;
int x[N] ;
int y[N] ;
int fac[N] ;
int inv[N] ;
int pres[N] ;
int sufs[N] ;
int expow(int a, int b){
int res = 1 ;
a = (a % P + P) % P ;
while (b){
if (b & 1)
res = (ll)res * a % P ;
a = (ll)a * a % P ; b >>= 1 ;
}
return res ;
}
int fz[N] ;
int fm[N] ;
int tmp[N] ;
int res[N] ;
void add(int &a, int b){
a += b ;
if (a > P) a -= P ;
}
void dec(int &a, int b){
(a -= b) %= P ;
if (a < 0) a += P ;
}
void fmul(int *t, int deg, int opt){
//次数为deg的多项式t乘上一个形如(x+opt)的多项式
for (int i = deg + 1 ; i >= 1 ; -- i)
tmp[i] = t[i], t[i] = t[i - 1] ;
for (int i = 1 ; i <= deg + 1 ; ++ i)
add(t[i], (ll)opt * tmp[i] % P) ;
}
void fdiv(int *t, int *ret, int deg, int opt){
//次数为deg的多项式除以一个形如(x+opt)的多项式(整除)
for (int i = 1 ; i <= deg ; ++ i) tmp[i] = t[i] ;
for (int i = deg - 1 ; i >= 1 ; -- i)
ret[i] = tmp[i + 1], dec(tmp[i], (ll)tmp[i + 1] * opt % P) ;
}
void get_xs(int n){//求系数
fz[1] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
fmul(fz, i, (-x[i] + P) % P) ;
//debug(fz, 1, n + 1, '\n') ;
for (int i = 1 ; i <= n ; ++ i){
int fenmu = 1 ;
for (int j = 1 ; j <= n ; ++ j)
if (i != j) fenmu = (ll)fenmu * (x[i] - x[j] + P) % P ;
fdiv(fz, fm, n + 1, -x[i]) ;
fenmu = (ll)y[i] * expow(fenmu, P - 2) % P ;
// cout << fenmu << endl ;
for (int j = 1 ; j <= n ; ++ j)
add(res[j], (ll)fenmu * fm[j] % P) ;
// debug(res, 1, n, '\n') ;
}
}
void pre_do(int U){
fac[0] = 1 ;
for (int i = 1 ; i <= U ; ++ i)
fac[i] = (ll)fac[i - 1] * i % P ;
inv[U] = expow(fac[U], P - 2) ;
for (int i = U ; i >= 1 ; -- i)
inv[i - 1] = (ll)inv[i] * i % P ;
//debug(fac, 1, U, '\n') ;
//debug(inv, 1, U, '\n') ;
}
int evenmark(int x){
return (x & 1) ? -1 : 1 ;
}
void get_dnx(int n, int k, bool m){
if (m){//求单独的一项，给出的x连续
pre_do(n) ;
pres[0] = 1, sufs[n + 1] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
pres[i] = ((ll)pres[i - 1] * (k - x[i]) % P + P) % P ;
for (int i = n ; i >= 1 ; -- i)
sufs[i] = ((ll)sufs[i + 1] * (k - x[i]) % P + P) % P ;
for (int i = 1 ; i <= n ; ++ i){
now = (ll)pres[i - 1] * sufs[i + 1] % P ;
now = (ll)now * expow((ll)fac[i - 1] * fac[n - i] % P, P - 2) % P ;
now = (ll)evenmark(n - i) * y[i] % P * now % P ; ans = (ll)(ans + now) % P ;
}
}
else {//求单独的一项，给出的x不连续
int inow = 1 ;
pres[0] = 1, sufs[n + 1] = 1 ;
for (int i = 1 ; i <= n ; ++ i)
pres[i] = ((ll)pres[i - 1] * (k - x[i]) % P + P) % P ;
for (int i = n ; i >= 1 ; -- i)
sufs[i] = ((ll)sufs[i + 1] * (k - x[i]) % P + P) % P ;
for (int i = 1 ; i <= n ; ++ i){
inow = 1, now = (ll)pres[i - 1] * sufs[i + 1] % P ;
for (int j = 1 ; j <= n ; ++ j)
if (i != j) inow = (ll)inow * ((x[i] - x[j]) % P + P) % P ;
ans = (ans + (ll)now * expow(inow, P - 2) % P * y[i] % P) % P ;
}
}
}
}
int main(){
cin >> n >> k ;
using namespace Interpolation ;
for (int i = 1 ; i <= n ; ++ i){
cin >> x[i] >> y[i] ;
if (x[i] == k) return cout << y[i], 0 ;
}
get_xs(n) ; //debug(res, 1, n + 1, '\n') ;
for (int i = n + 1 ; i >= 1 ; -- i)
ans = ((ll)ans * k % P + res[i]) % P ;
cout << ans << '\n' ; return 0 ;
}
```