AT_fps_24_x.関数的平方根

给定一个形式幂级数 $F(x) = \sum_{i=0}^{N-1} f_i x^i$，其定义在 $\mathbb{F}_{998244353}$ 上，其中 $N \geq 2$ 且 $F(x) \bmod x^2 = x$。

可以证明，存在唯一的形式幂级数 $G(x) = \sum_{i=0}^{N-1} g_i x^i$，其定义在 $\mathbb{F}_{998244353}$ 上，满足：

• $G(G(x)) \equiv F(x) \pmod{x^N}$；
• $G(x) \bmod x^2 = x$。

你的任务是求出这个 $G(x)$。

输入由标准输入给出，格式如下：

$N$ $f_0$ $f_1$ $\dots$ $f_{N-1}$

请按如下格式输出答案：

$g_0$ $g_1$ $\dots$ $g_{N-1}$

提示

本题为难度极高的挑战题，适合完成所有其他题目后仍有余力的同学尝试。
本题分值相对难度略低。
建议优先完成其他题目。

样例解释 1

$G(x) = x + 2x^2$ 满足所有条件。

数据范围

• $2 \leq N \leq 8000$
• $f_0 = 0$
• $f_1 = 1$
• $0 \leq f_i < 998244353$，对 $2 \leq i \leq N-1$
• 所有输入值均为整数。

由 ChatGPT 5 翻译