Nghịch Đảo Đa Thức Modulo x^N

Buổi 60 — FFT / NTT
Points
55
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Submissions
Đề 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$
Draft saved