多项式插值

【题目描述】

给定整数序列 $x_0, x_1, ..., x_{N - 1}$ 和 $y_0, y_1, ..., y_{N - 1}$。

请计算一个多项式 $f(x) = \sum_{i = 0}^{N - 1} c_i x^i \in \mathbb{Z}[x]$，使得对于每个 $i$ 都满足 $f(x_i) \equiv y_i \pmod{998244353}$。

此外，还必须满足 $0 \leq c_i < 998244353$。

【输入】

输入格式如下：

$N$
$x_0$ $x_1$ ... $x_{N-1}$
$y_0$ $y_1$ ... $y_{N-1}$

【输出】

输出格式如下：

$c_0$ $c_1$ ... $c_{N -1}$

【输入样例】

5
5 6 7 8 9
586 985 1534 2257 3178

【输出样例】

1 2 3 4 0

【输入样例2】

1
10000000
10000000

【输出样例2】

10000000

【数据范围】

• $1 \leq N \leq 2^{17}(=131072)$
• $0 \leq x_i, y_i < 998244353$
• $x_i \neq x_j (i \neq j)$

【来源】

Library Checker（yosupo06） polynomial_interpolation