Problem11302--[yosupo] Polynomial - Product of Polynomial Sequence

11302: [yosupo] Polynomial - Product of Polynomial Sequence

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 512 MiB

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$. 

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}}$

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$

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

HINT

Source/Category