Composition of Formal Power Series

AC一覧

Problem Statement
問題文

Given formal power series $f(x) = \sum_{i = 0}^{N - 1} a_i x^i$ and $g(x) = \sum_{i = 0}^{N - 1} b_i x^i$. Calculate first $N$ terms of $f(g(x))$,in other words, find

$h(x)=\sum_{i=0}^{N-1} a_i g(x)^i \bmod (x^N)$ and output the coefficients modulo $998{,}244{,}353$.

形式的冪級数 $f(x) = \sum_{i = 0}^{N - 1} a_i x^i$ と $g(x) = \sum_{i = 0}^{N - 1} b_i x^i$ が与えられます。 $f(g(x))$ の先頭$N$項を求めてください。つまり

$h(x)=\sum_{i=0}^{N-1} a_i g(x)^i \bmod (x^N)$となる$h(x)$を求めて、係数を modulo $998{,}244{,}353$ で出力してください

Constraints
制約

Input
入力

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

Output
出力

$c_0$ $c_1$ ... $c_{N - 1}$

If we denote $h(x)=\sum_{i = 0}^{(N - 1)} c'_i x^i$,$c_i \equiv c'_i(\bmod{998{,}244{,}353})$ is satisfied.

ただし、$h(x)=\sum_{i = 0}^{(N - 1)} c'_i x^i$とした時$c_i \equiv c'_i(\bmod 998{,}244{,}353)$である。

Sample
サンプル

# 1

5
5 4 3 2 1
0 1 2 3 4
5 4 11 26 59

Timelimit: 10 secs

Before submitting, please confirm terms and conditions