Lũy Thừa Đa Thức Cắt Ngọn
Points
35
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Đề 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$
Community Discussion