Logarit Tự Nhiên Đa Thức Modulo x^N

Buổi 60 — FFT / NTT Mathematics
Points
65
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Cho đa thức hình thức $P(x) = \sum_{i=0}^{N-1} a_i x^i$ có hệ số nguyên thỏa mãn $a_0 = 1$. Dưới vành chuỗi lũy thừa hình thức modulo $998244353$, logarit tự nhiên của $P(x)$ được định nghĩa thông qua đạo hàm và tích phân hình thức: \[\ln P(x) \equiv \int_0^x \frac{P'(t)}{P(t)} \, dt \pmod{x^N}\] Hãy tính $N$ hệ số đầu tiên $b_0, b_1, \dots, b_{N-1}$ của $\ln P(x) \bmod x^N$ theo 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 3 4
0 2 1 665496236
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved