Problem11325--[yosupo] Polynomial - Composition of Formal Power Series (Large)

11325: [yosupo] Polynomial - Composition of Formal Power Series (Large)

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

Description

You are given two formal power series $f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{F}\_{998244353}[[x]]$ and $g(x) = \sum_{i=0}^{N-1} b_i x^i \in \mathbb{F}\_{998244353}[[x]]$ with $b_0 = 0$.
Calculate the first $N$ terms of $f(g(x)) = \sum_{i=0}^{\infty} c_i x^i$.
In other words, find $h(x) = \sum_{i=0}^{N-1} c_i x^i \in \mathbb{F}\_{998244353}[[x]]$ such that

$h(x) \equiv \sum_{i=0}^{N-1} a_i g(x)^i \pmod{x^N}.$

Input

$N$
$a_0$ $a_1$ $\cdots$ $a_{N - 1}$
$b_0$ $b_1$ $\cdots$ $b_{N - 1}$

Output

$c_0$ $c_1$ $\cdots$ $c_{N - 1}$

Constraints

- $1 \leq N \leq 2^{17}$
- $0 \leq a_i, b_i < 998244353$
- $b_0 = 0$

Sample 1 Input

5
5 4 3 2 1
0 1 2 3 4

Sample 1 Output

5 4 11 26 59

HINT

Yosupo.

Source/Category