P4083【模板】拉格朗日插值 | ||
|
問題説明
这是一道模板题。
由小学知识可知 \(n\) 个点 \((x_i,y_i)\) 可以唯一地确定一个多项式 \(y=f(x)\)。
现在,给定这 \(n\) 个点,请你确定这个多项式,并求出 \(f(k) \; mod \; 998244353\) 的值。
入力形式
第一行两个整数 \(n\),\(k\)。
接下来 \(n\) 行,第 \(i\) 行两个整数 \(x_i\),\(y_i\)。
出力形式
一行一个整数,表示 \(f(k) \; mod \; 998244353\) 的值。
サンプル入力 1
3 100
1 4
2 9
3 16
サンプル出力 1
10201
サンプル入力 2
3 100
1 1
2 2
3 3
サンプル出力 2
100
ヒント
样例一中的多项式为 \(f(x)=x^2+2x+1\),\(f(100)=10201\)。
样例二中的多项式为 \(f(x)=x\),\(f(100)=100\)。
$1 \le n \le 2 \times 10^3$,$1 \le x_i,y_i,k < 998244353$,\(x_i\) 两两不同。