P5205 [Template] Polynomial Square Root.

This is a template problem, with no background.

Given a polynomial $A(x)$ of degree $n - 1$, find a polynomial $B(x)$ modulo $x^n$ such that $B^2(x) \equiv A(x) \pmod{x^n}$. If there are multiple solutions, output the one with the smaller constant-term coefficient. All polynomial coefficients are computed modulo $998244353$.

The first line contains a positive integer $n$. The next line contains $n$ integers, representing the coefficients $a_0, a_1, \dots, a_{n-1}$ of the polynomial in order. It is guaranteed that $a_0 = 1$.

Output $n$ integers, representing the coefficients $b_0, b_1, \dots, b_{n-1}$ of the answer polynomial.

For $100\%$ of the testdata: $1 \le n \le 10^5$, $0 \le a_i < 998244353$. Translated by ChatGPT 5