/ 
Time Limit: 12 sec / Memory Limit: 1024 MiB
配点 : 1 点
注記
この問題は 他の問題を通し終えて暇になった人向けの難問 です。配点も難易度に比べてかなり低めに設定されています。
他の問題を通していない方は先に他の問題を通すことを推奨します。
問題文
\mathbb{F} _ {998244353} 係数の形式的冪級数 F(x) = \sum_{i=0}^{N-1} f_i x^i が与えられます。ここで N \geq 2 かつ F(x) \bmod{x^2} = x が成り立ちます。この時、
- G(G(x)) \equiv F(x) \pmod{x^N} かつ
- G(x) \bmod{x^2} = x
を満たす \mathbb{F} _ {998244353} 係数の形式的冪級数 G(x) = \sum_{i=0}^{N-1} g_i x^i は存在して、かつ一意に定まります。この G(x) を求めてください。
制約
- 2 \leq N \leq 8000
- f_0 = 0
- f_1 = 1
- 0 \leq f_i \lt 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
Score: 1 points
Note
This problem is a hard challenge intended for those who have finished all other problems and still have time left.
The score is set relatively low compared to its difficulty.
If you have not solved the other problems yet, it is recommended to do those first.
Problem Statement
You are given a formal power series F(x) = \sum_{i=0}^{N-1} f_i x^i over \mathbb{F} _ {998244353}, where N \geq 2 and F(x) \bmod{x^2} = x.
It can be proven that there exists a unique formal power series G(x) = \sum_{i=0}^{N-1} g_i x^i over \mathbb{F} _ {998244353} such that:
- G(G(x)) \equiv F(x) \pmod{x^N}, and
- G(x) \bmod{x^2} = x.
Your task is to find this G(x).
Constraints
- 2 \leq N \leq 8000
- f_0 = 0
- f_1 = 1
- 0 \leq f_i < 998244353 for 2 \leq i \leq N-1
- All input values are integers
Input
The input is given from standard input in the following format:
N
f_0 f_1 \dots f_{N-1}
Output
Print the answer in the following format:
g_0 g_1 \dots g_{N-1}
Sample Input 1
3 0 1 4
Sample Output 1
0 1 2
G(x) = x + 2x^2 satisfies the conditions.
Sample Input 2
7 0 1 766294629 440423913 59187619 725560240 585990756
Sample Output 2
0 1 882269491 824730961 772850352 694658399 134447547