Sqrt of Formal Power Series

AC一覧

Problem Statement
問題文

Given formal power series $f(x) = \sum_{i = 0}^{N - 1} a_i x^i$. Calculate first $N$ elements of $\sqrt{f(x)}$. In other words, print $g(x)$ s.t.

$$f(x) = g(x) \times g(x) \bmod (x^N)$$

is satisfied. We consider everything in $\mathbb{Z}_{998{,}244{,}353}$.

母関数 $f(x) = \sum_{i = 0}^{N - 1} a_i x^i$ が与えられます。$\sqrt{f(x)}$ の先頭 $N$ 項を求めてください。つまり

$$f(x) = g(x) \times g(x) \bmod (x^N)$$

となる $g(x)$ を出力してください。ただし係数は全て $\mathbb{Z}_{998{,}244{,}353}$ とします

Constraints
制約

Input
入力

$N$
$a_0$ $a_1$ ... $a_{N - 1}$

Output
出力

If there are no $g(x)$, print

条件を満たす $g(x)$ が存在しない場合、

-1

and if exists, print

と出力してください。

存在する場合、

$b_0$ $b_1$ ... $b_{N - 1}$

We denote $g(x) = \sum_{i = 0}^{N - 1} b_i x^i$.

If there are multiple solutions, print any of them.

と出力してください。ただし $g(x) = \sum_{i = 0}^{N - 1} b_i x^i$ とします。

なお、条件を満たすものが複数ある場合、どれか 1 つを選び出力してください。

Sample
サンプル

# 1

4
0 0 9 12
0 3 2 332748117

# 2

4
0 0 10 12
-1

Forum


Timelimit: 10 secs

Before submitting, please confirm terms and conditions