Hàm Mũ Đa Thức

Buổi 60 — FFT / NTT
Points
88
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$ thỏa mãn $p_0 = 0$. Hãy tính $N$ hệ số đầu tiên của đa thức $\exp(P(x)) = \sum_{k=0}^{\infty} \frac{P(x)^k}{k!} \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 = 0$).
Dữ liệu ra

In ra $N$ số nguyên là các hệ số của $\exp(P(x)) \bmod x^N \bmod 998244353$.

Ví dụ
Input Output
4
0 1 0 0
1 1 499122177 166374059
1
0
1
Giới hạn
  • $1 \le N \le 10^5$
Draft saved