11294: [yosupo] Polynomial - Sqrt of Formal Power Series
[Creator : ]
Description
You are given a formal power series $f(x) = \sum_{i=0}^{N-1} a_i x^i \in \mathbb{F}\_{998244353}[[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}\_{998244353}[[x]]$ such that
$f(x) \equiv g(x)^2 \pmod{x^N}.$
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}\_{998244353}[[x]]$ such that
$f(x) \equiv g(x)^2 \pmod{x^N}.$
Input
$a_0$ $a_1$ $\cdots$ $a_{N - 1}$
Output
If there are no $g(x)$ satisfying the condition, print
-1
and if such $g(x)$ exists, choose any and print
$b_0$ $b_1$ $\cdots$ $b_{N - 1}$
-1
and if such $g(x)$ exists, choose any and print
$b_0$ $b_1$ $\cdots$ $b_{N - 1}$
Constraints
- $1 \leq N \leq 5\times 10^5$
- $0 \leq a_i < 998244353$
- $0 \leq a_i < 998244353$
Sample 1 Input
4
0 0 9 12
Sample 1 Output
0 3 2 332748117
Sample 2 Input
4
0 0 10 12
Sample 2 Output
-1