多点求值

【题目描述】

给定多项式 $f(x) = \sum_{i = 0}^{N - 1} c_i x^i \in \mathbb{Z}[x]$ 和整数序列 $p_0, p_1, ..., p_{M - 1}$。 对每个 $p_i$，输出 $f(p_i) \bmod 998244353$。

【输入】

$N$ $M$
$c_0$ $c_1$ ... $c_{N-1}$
$p_0$ $p_1$ ... $p_{M-1}$

【输出】

$f(p_0)$ $f(p_1)$ ... $f(p_{M-1})$

【输入样例】

4 5
1 2 3 4
5 6 7 8 9

【输出样例】

586 985 1534 2257 3178

【输入样例2】

1 1
10000000
10000000

【输出样例2】

10000000

【数据范围】

• $1 \leq N, M \leq 2^{17}(=131072)$
• $0 \leq c_i, p_i < 998244353$
• $c_{N - 1} \neq 0$

【来源】

Library Checker（yosupo06） multipoint_evaluation