11316: [yosupo] Polynomial - Multipoint Evaluation (Geometric Sequence)
[Creator : ]
Description
Given a polynomial $f(x) = \sum_{i = 0}^{N - 1} c_i x^i\in \mathbb{Z}[x]$ and integers $M, a, r$.
Print $f(ar^i) \bmod 998244353$ for each $0\leq i < M$.
Print $f(ar^i) \bmod 998244353$ for each $0\leq i < M$.
Input
$N$ $M$ $a$ $r$
$c_0$ $c_1$ ... $c_{N-1}$
$c_0$ $c_1$ ... $c_{N-1}$
Output
$f(ar^0)$ $f(ar^1)$ ... $f(ar^{M-1})$
Constraints
- $1 \leq N, M \leq 2^{19}$
- $0 \leq a, r < 998244353$
- $0 \leq a, r < 998244353$
Sample 1 Input
5 4 3 2
1 2 3 4 5
Sample 1 Output
547 7465 111049 1715953
Sample 2 Input
3 4 2 0
3 2 0
Sample 2 Output
7 3 3 3