Đến nội dung chính

canuc80k7100·1/16

Giá Trị Qua Các Điểm

Nộp bài trên LQDOJ

Bài 71 · Lagrange Interpolation

Mọi phép tính trong bài được thực hiện theo modulo $998244353$ .

Cho $n$ cặp số $(x_{i}, y_{i})$ , trong đó các $x_{i}$ đôi một khác nhau. Có duy nhất một đa thức $f$ bậc không quá $n - 1$ thỏa mãn

f (x_{i}) \equiv y_{i} (mod 998244353)

với mọi $i$ . Hãy tính $f (k)$ .

Input

Dòng đầu chứa hai số nguyên $n$ và $k$ .
Mỗi dòng trong $n$ dòng tiếp theo chứa hai số nguyên $x_{i}, y_{i}$ .

Output

In một số nguyên trong đoạn $[0, 998244352]$ bằng $f (k)$ modulo $998244353$ .

Constraints

$1 \leq n \leq 2000$ .
$1 \leq k, x_{i}, y_{i} < 998244353$ .
Các giá trị $x_{i}$ đôi một khác nhau.

Scoring

Subtask $1$ ( $50%$ số điểm): $n \leq 12$ .
Subtask $2$ ( $50%$ số điểm): Không có giới hạn bổ sung.

Example

Test 1

Input

2 4
1 5
2 7

Output

Giải thích: Hai điểm xác định đa thức $f (x) = 2 x + 3$ , vì vậy $f (4) = 11$ .

Test 2

Input

Output

Giải thích: Điểm cần hỏi trùng với hoành độ của cặp thứ ba, nên giá trị cần in chính là $y_{3} = 26$ .

Lời giải tóm tắt

Ý tưởng: Với mỗi điểm thứ i, xét đa thức cơ sở
Ý tưởng: [ L_i(x)=\prod_{j\ne i}\frac{x-x_j}{x_i-x_j}. ]
Ý tưởng: Ta có L_i(x_i)=1 và L_i(x_j)=0 khi j≠i. Vì vậy
Ý tưởng: [ f(x)=\sum_{i=1}^{n} y_iL_i(x). ]
Ý tưởng: Mẫu số khác 0 modulo 998244353 vì các hoành độ đôi một khác nhau; nghịch đảo được tính bằng định lý Fermat nhỏ. Nếu k trùng một x_i, trả trực tiếp y_i.
Ý tưởng: Độ phức tạp là O(n^2+n log MOD) thời gian và O(n) bộ nhớ.