Nghịch Đảo Đa Thức Modulo x^N
Points
55
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Đề bài
Cho đa thức $P(x) = \sum_{i=0}^{N-1} p_i x^i$ với $p_0 \neq 0$. Hãy tìm đa thức nghịch đảo $Q(x) = \sum_{i=0}^{N-1} q_i x^i$ sao cho $P(x) \cdot Q(x) \equiv 1 \pmod{x^N}$ với các hệ số modulo $998244353$.
Dữ liệu vào
- Dòng đầu chứa số nguyên $N$ ($1 \le N \le 10^5$).
- Dòng thứ hai chứa $N$ số nguyên $p_0, p_1, \dots, p_{N-1}$ ($0 \le p_i < 998244353$, $p_0 \neq 0$).
Dữ liệu ra
In ra $N$ số nguyên $q_0, q_1, \dots, q_{N-1}$ cách nhau bởi dấu cách.
Ví dụ
| Input | Output |
|---|---|
| 4 1 1 0 0 |
1 998244352 1 998244352 |
| 3 2 4 6 |
499122177 998244352 499122177 |
Giới hạn
- $1 \le N \le 10^5$
Community Discussion