11300: [yosupo] Polynomial - Pow of Formal Power Series (Sparse)
[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$.
Only $K$ coefficients of $f$ are non-zero, and only such coefficients $a_{i_k}$ are given from input.
Calculate the first $N$ terms of $(f(x))^M = \sum_{i=0}^{\infty} b_i x^i$.
Only $K$ coefficients of $f$ are non-zero, and only such coefficients $a_{i_k}$ are given from input.
Calculate the first $N$ terms of $(f(x))^M = \sum_{i=0}^{\infty} b_i x^i$.
Input
$N$ $K$ $M$
$i_0$ $a_{i_0}$
$\vdots$
$i_{K-1}$ $a_{i_{K-1}}$
$i_0$ $a_{i_0}$
$\vdots$
$i_{K-1}$ $a_{i_{K-1}}$
Output
$b_0$ $b_1$ $\cdots$ $b_{N - 1}$
Constraints
- $1 \leq N \leq 10^6$
- $0 \leq K \leq 10$
- $0 \leq M \leq 10^{18}$
- $0 \leq i_0 < \cdots < i_{K-1} \leq N - 1$
- $1 \leq a_{i_k} < 998244353$
- $0 \leq K \leq 10$
- $0 \leq M \leq 10^{18}$
- $0 \leq i_0 < \cdots < i_{K-1} \leq N - 1$
- $1 \leq a_{i_k} < 998244353$
Sample 1 Input
5 2 3
0 1
2 1
Sample 1 Output
1 0 3 0 3
Sample 2 Input
5 2 3
1 1
2 1
Sample 2 Output
0 0 0 1 3
Sample 3 Input
5 0 10
Sample 3 Output
0 0 0 0 0
5 0 0
1 0 0 0 0