11302: [yosupo] Polynomial - Product of Polynomial Sequence
[Creator : ]
Description
$N$ polynomials $f_i(x) = \sum_{j=0}^{d_j} a_{i,j} x^{j} \in \mathbb{Z}[x]$ ($i=0,\ldots,N-1$) are given.
Compute $f(x) = \prod_{i=0}^{N-1} f_i(x)$ modulo $998244353$.
Compute $f(x) = \prod_{i=0}^{N-1} f_i(x)$ modulo $998244353$.
Input
$N$
$d_0$ $a_{0,0}$ $\ldots$ $a_{0,d_0}$
$\vdots$
$d_{N-1}$ $a_{N-1,0}$ $\ldots$ $a_{N-1,d_{N-1}}$
$d_0$ $a_{0,0}$ $\ldots$ $a_{0,d_0}$
$\vdots$
$d_{N-1}$ $a_{N-1,0}$ $\ldots$ $a_{N-1,d_{N-1}}$
Output
$a_0$ $a_1$ ... $a_{D}$
Here $D = \sum_{i=0}^{N-1} d_i$ and $f(x) = \sum_{j=0}^{D} a_jx^j \pmod{998244353}$.
Constraints
- $0 \leq N \leq 5\times 10^5$
- $0 \leq d_{i}$ and $\sum_{i=0}^{N-1} d_i \leq 5\times 10^5$
- $0 \leq a_{i,j} < 998244353$
- $a_{i, d_i}\neq 0$
- $0 \leq d_{i}$ and $\sum_{i=0}^{N-1} d_i \leq 5\times 10^5$
- $0 \leq a_{i,j} < 998244353$
- $a_{i, d_i}\neq 0$
Sample 1 Input
3
0 2
1 1 2
2 3 2 1
Sample 1 Output
6 16 10 4
$f(x) = 2(1+2x)(3+2x+x^2) = 6+16x+10x^2+4x^3$.
Sample 2 Input
1
2 3 4 5
Sample 2 Output
3 4 5
Sample 3 Input
0
Sample 3 Output
1