Polynomial Interpolation

AC一覧

Problem Statement
問題文

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$ s.t. $f(x_i) \equiv y_i (\bmod 998244353)$ is satisfied for each $i$.

Also, $0 \leq c_i < 998244353$ must be satisfied.

整数列 $x_0, x_1, ..., x_{N - 1}$、$y_0, y_1, ..., y_{N - 1}$ が与えられます。

全ての $i$ について $f(x_i) \equiv y_i (\bmod 998244353)$ を満たす多項式 $f(x) = \sum_{i = 0}^{N - 1} c_i x^i$ を求めてください。 ただし $0 \leq c_i < 998244353$ とします。

Constraints
制約

Input
入力

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

Output
出力

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

Sample
サンプル

# 1

5
5 6 7 8 9
586 985 1534 2257 3178
1 2 3 4 0

# 2

1
10000000
10000000
10000000

Forum


Timelimit: 10 secs

Before submitting, please confirm terms and conditions