11293: [yosupo] Polynomial - Pow of Formal Power Series
[Creator : ]
Description
You are given a formal power series $f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{F}\_{998244353}[[x]]$ and a non-negative integer $M$.
Calculate the first $N$ terms of $(f(x))^M = \sum_{i=0}^{\infty} b_i x^i$.
Calculate the first $N$ terms of $(f(x))^M = \sum_{i=0}^{\infty} b_i x^i$.
Input
$N$ $M$
$a_0$ $a_1$ $\cdots$ $a_{N-1}$
$a_0$ $a_1$ $\cdots$ $a_{N-1}$
Output
$b_0$ $b_1$ $\cdots$ $b_{N - 1}$
Constraints
- $1 \leq N \leq 5\times 10^5$
- $0 \leq M \leq 10^{18}$
- $0 \leq a_i < 998244353$
- $0 \leq M \leq 10^{18}$
- $0 \leq a_i < 998244353$
Sample 1 Input
4 3
0 0 9 12
Sample 1 Output
0 0 0 0
Sample 2 Input
2 2
1 1
Sample 2 Output
1 2
Sample 3 Input
2 0
0 0
Sample 3 Output
1 0