Composition of Formal Power Series

AC一覧

Problem Statement
問題文

You are given two formal power series $f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{F}_{998{,}244{,}353}[[x]]$ and $g(x) = \sum_{i=0}^{N-1} b_i x^i \in \mathbb{F}_{998{,}244{,}353}[[x]]$ with $b_0 \ne 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}_{998{,}244{,}353}[[x]]$ such that

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

形式的冪級数 $f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{F}_{998{,}244{,}353}[[x]]$ と $g(x) = \sum_{i=0}^{N-1} b_i x^i \in \mathbb{F}_{998{,}244{,}353}[[x]]$ が与えられます ($b_0 = 0$)。$f(g(x)) = \sum_{i=0}^{\infty} c_i x^i$ の先頭 $N$ 項を求めてください。つまり、

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

となる $h(x) = \sum_{i=0}^{N-1} c_i x^i \in \mathbb{F}_{998{,}244{,}353}[[x]]$ を求めてください。

Constraints
制約

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

Sample
サンプル

# 1

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

Forum


Timelimit: 10 secs

Before submitting, please confirm terms and conditions