Căn Bậc Hai Đa Thức Modulo x^N
Points
70
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
number
Đề bài
Cho đa thức hình thức $P(x) = \sum_{i=0}^{N-1} a_i x^i$ với hệ số trên trường số nguyên modulo $998244353$ và có hệ số tự do $a_0 = 1$. Hãy tìm đa thức $Q(x) = \sum_{i=0}^{N-1} b_i x^i$ sao cho $b_0 = 1$ và thỏa mãn đồng dư thức đa thức: \[Q(x)^2 \equiv P(x) \pmod{x^N}\] với các hệ số được lấy modulo $998244353$.
Dữ liệu vào
Dòng đầu tiên chứa số nguyên $N$ ($1 \le N \le 10^5$). Dòng thứ hai chứa $N$ số nguyên $a_0, a_1, \dots, a_{N-1}$ ($0 \le a_i < 998244353$, với $a_0 = 1$).
Dữ liệu ra
In ra $N$ số nguyên $b_0, b_1, \dots, b_{N-1}$ trong đoạn $[0, 998244352]$ cách nhau bởi dấu cách.
Ví dụ
| Input | Output |
|---|---|
| 4 1 2 1 0 |
1 1 0 0 |
Giới hạn
Thời gian: 1.0s, Bộ nhớ: 256MB.
Community Discussion