11323: [yosupo] Polynomial - Conversion from Monomial Basis to Newton Basis
[Creator : ]
Description
You are given a polynomial $\displaystyle f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{Z}[x]$ and integers $p_0, p_1, \ldots, p_{N-1}$.
Find $b_0, b_1, \ldots, b_{N-1}$ such that $\displaystyle f(x) = \sum_{i=0}^{N-1} b_i \prod_{j=0}^{i-1} (x-p_j)$ and print them modulo $998244353$.
Find $b_0, b_1, \ldots, b_{N-1}$ such that $\displaystyle f(x) = \sum_{i=0}^{N-1} b_i \prod_{j=0}^{i-1} (x-p_j)$ and print them modulo $998244353$.
Input
$N$
$a_0$ $a_1$ $\cdots$ $a_{N-1}$
$p_0$ $p_1$ $\cdots$ $p_{N-1}$
$a_0$ $a_1$ $\cdots$ $a_{N-1}$
$p_0$ $p_1$ $\cdots$ $p_{N-1}$
Output
$b_0$ $b_1$ $\cdots$ $b_{N-1}$
Constraints
- $0 \leq N \leq 2^{17}$
- $0 \leq a_i, p_i \lt 998244353$
- $0 \leq a_i, p_i \lt 998244353$
Sample 1 Input
5
1 10 100 1000 10000
0 1 2 3 4
Sample 1 Output
1 11110 73100 61000 10000