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

输入 #1

3
0 1 4

输出 #1

0 1 2

输入输出样例 #2

输入 #2

7
0 1 766294629 440423913 59187619 725560240 585990756

输出 #2

0 1 882269491 824730961 772850352 694658399 134447547

说明/提示

提示

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

样例解释 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 翻译