Sqrt of Formal Power Series

AC一覧

Problem Statement
問題文

You are given a formal power series $f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{F}_{998{,}244{,}353}[[x]]$. Calculate the first $N$ terms of a square root of $f(x)$. In other words, find $g(x) = \sum_{i=0}^{N-1} b_i x^i \in \mathbb{F}_{998{,}244{,}353}[[x]]$ such that

$$f(x) \equiv g(x)^2 \pmod{x^N}.$$

形式的冪級数 $f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{F}_{998{,}244{,}353}[[x]]$ が与えられます。$f(x)$ の平方根の $1$ つの先頭 $N$ 項を求めてください。つまり、

$$f(x) \equiv g(x)^2 \pmod{x^N}$$

となる $g(x) = \sum_{i=0}^{N-1} b_i x^i \in \mathbb{F}_{998{,}244{,}353}[[x]]$ を求めてください。

Constraints
制約

Input
入力

$N$
$a_0$ $a_1$ $\cdots$ $a_{N - 1}$

Output
出力

If there are no $g(x)$ satisfying the condition, print

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

-1

and if such $g(x)$ exists, choose any and print

と出力してください。

存在する場合、どれか $1$ つを選び、

$b_0$ $b_1$ $\cdots$ $b_{N - 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