11315: [yosupo] Polynomial - Multipoint Evaluation
[Creator : ]
Description
Given a polynomial $f(x) = \sum_{i = 0}^{N - 1} c_i x^i \in \mathbb{Z}[x]$ and integer sequence $p_0, p_1, ..., p_{M - 1}$.
Print $f(p_i) \bmod 998244353$ for each $p_i$.
Print $f(p_i) \bmod 998244353$ for each $p_i$.
Input
$N$ $M$
$c_0$ $c_1$ ... $c_{N-1}$
$p_0$ $p_1$ ... $p_{M-1}$
$c_0$ $c_1$ ... $c_{N-1}$
$p_0$ $p_1$ ... $p_{M-1}$
Output
$f(p_0)$ $f(p_1)$ ... $f(p_{M-1})$
Constraints
- $1 \leq N, M \leq 2^{17}(=131072)$
- $0 \leq c_i, p_i < 998244353$
- $c_{N - 1} \neq 0$
- $0 \leq c_i, p_i < 998244353$
- $c_{N - 1} \neq 0$
Sample 1 Input
4 5
1 2 3 4
5 6 7 8 9
Sample 1 Output
586 985 1534 2257 3178
Sample 2 Input
1 1
10000000
10000000
Sample 2 Output
10000000