← 返回题目列表

AtCoder · fps_24_x

X. 函数平方根

中文机器翻译题面 查看原题

分数: 1 点

注意

这个问题是 为那些已完成所有其他问题且仍有时间的人设计的困难挑战.
与难度相比,分数设置相对较低。
如果您还没有解决其他问题,建议先解决这些问题。

问题陈述

你得到了一个正式的幂级数 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).

约束

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

输入

输入由标准输入给出,格式如下:

N
f_0 f_1 \dots f_{N-1}

输出

按以下格式打印答案:

g_0 g_1 \dots g_{N-1}

样本输入 1

3
0 1 4

示例输出 1

0 1 2

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


示例输入 2

7
0 1 766294629 440423913 59187619 725560240 585990756

示例输出 2

0 1 882269491 824730961 772850352 694658399 134447547