11317: [yosupo] Polynomial - Polynomial Interpolation
[Creator : ]
Description
Given integer sequences $x_0, x_1, ..., x_{N - 1}$ and $y_0, y_1, ..., y_{N - 1}$.
Calculate a polynomial $f(x) = \sum_{i = 0}^{N - 1} c_i x^i \in \mathbb{Z}[x]$ s.t. $f(x_i) \equiv y_i (\bmod 998244353)$ is satisfied for each $i$.
Also, $0 \leq c_i < 998244353$ must be satisfied.
Calculate a polynomial $f(x) = \sum_{i = 0}^{N - 1} c_i x^i \in \mathbb{Z}[x]$ s.t. $f(x_i) \equiv y_i (\bmod 998244353)$ is satisfied for each $i$.
Also, $0 \leq c_i < 998244353$ must be satisfied.
Input
$N$
$x_0$ $x_1$ ... $x_{N-1}$
$y_0$ $y_1$ ... $y_{N-1}$
$x_0$ $x_1$ ... $x_{N-1}$
$y_0$ $y_1$ ... $y_{N-1}$
Output
$c_0$ $c_1$ ... $c_{N -1}$
Constraints
- $1 \leq N \leq 2^{17}(=131072)$
- $0 \leq x_i, y_i < 998244353$
- $x_i \neq x_j (i \neq j)$
- $0 \leq x_i, y_i < 998244353$
- $x_i \neq x_j (i \neq j)$
Sample 1 Input
5
5 6 7 8 9
586 985 1534 2257 3178
Sample 1 Output
1 2 3 4 0
Sample 2 Input
1
10000000
10000000
Sample 2 Output
10000000