分数: 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