Lũy Thừa Đa Thức Cắt Ngọn

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

Cho đa thức $P(x)$ bậc $D$ ($0 \le D < N$) và số nguyên không âm $K$. Hãy tính $N$ hệ số đầu tiên (từ $x^0$ đến $x^{N-1}$) của $P(x)^K \bmod x^N$ với các hệ số lấy modulo $998244353$. Quy ước $P(x)^0 = 1$.

Dữ liệu vào
  • Dòng đầu chứa ba số nguyên $D, N, K$ ($0 \le D < N \le 10^5$, $0 \le K \le 10^9$).
  • Dòng thứ hai chứa $D + 1$ số nguyên $p_0, p_1, \dots, p_D$ ($0 \le p_i < 998244353$).
Dữ liệu ra

In ra $N$ số nguyên là các hệ số của $x^0, x^1, \dots, x^{N-1}$ trong $P(x)^K \bmod x^N \bmod 998244353$.

Ví dụ
Input Output
1 4 3
1 1
1 3 3 1
2 5 0
2 3 4
1 0 0 0 0
Giới hạn
  • $0 \le D < N \le 10^5$
  • $0 \le K \le 10^9$
Draft saved