11326: [yosupo] Polynomial - Compositional Inverse of Formal Power Series (Large)
[Creator : ]
Description
You are given a formal power series $f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{F}\_{998244353}[[x]]$ with $a_0 = 0, a_1 \neq 0$.
Calculate the first $N$ terms of $f^{\langle -1 \rangle}(x) = \sum_{i=0}^{\infty} b_i x^i$ with $b_0 = 0$.
In other words, find $g(x) = \sum_{i=0}^{N-1} b_i x^i \in \mathbb{F}\_{998244353}[[x]]$ such that
$
f(g(x)) \equiv g(f(x)) \equiv x \pmod{x^{N}}
$
Print the coefficients modulo $998244353$.
Calculate the first $N$ terms of $f^{\langle -1 \rangle}(x) = \sum_{i=0}^{\infty} b_i x^i$ with $b_0 = 0$.
In other words, find $g(x) = \sum_{i=0}^{N-1} b_i x^i \in \mathbb{F}\_{998244353}[[x]]$ such that
$
f(g(x)) \equiv g(f(x)) \equiv x \pmod{x^{N}}
$
Print the coefficients modulo $998244353$.
Input
$N$
$a_0$ $a_1$ $\cdots$ $a_{N - 1}$
$a_0$ $a_1$ $\cdots$ $a_{N - 1}$
Output
$b_0$ $b_1$ $\cdots$ $b_{N - 1}$
Constraints
- $2 \leq N \leq 2^{17}$
- $0 \leq a_i < 998244353$
- $a_0 = 0$
- $a_1 \neq 0$
- $0 \leq a_i < 998244353$
- $a_0 = 0$
- $a_1 \neq 0$
Sample 1 Input
5
0 1 2 3 4
Sample 1 Output
0 1 998244351 5 998244339