Chia Đa Thức Lấy Dư
Points
75
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Đề bài
Cho đa thức $A(x)$ bậc $N$ và đa thức $B(x)$ bậc $M$ ($0 \le M \le N \le 10^5$, hệ số bậc cao nhất $b_M \neq 0$). Hãy tìm đa thức thương $Q(x)$ và đa thức dư $R(x)$ (bậc $< M$) sao cho $A(x) \equiv B(x)Q(x) + R(x) \pmod{998244353}$.
Dữ liệu vào
- Dòng đầu chứa hai số nguyên $N, M$ ($0 \le M \le N \le 10^5$).
- Dòng thứ hai chứa $N + 1$ số nguyên $a_0, \dots, a_N$ ($0 \le a_i < 998244353$).
- Dòng thứ ba chứa $M + 1$ số nguyên $b_0, \dots, b_M$ ($0 \le b_j < 998244353$, $b_M \neq 0$).
Dữ liệu ra
- Dòng đầu in ra $N - M + 1$ số nguyên là các hệ số của $Q(x)$ từ bậc $0$ đến $N - M$.
- Dòng thứ hai in ra $M$ số nguyên là các hệ số của $R(x)$ từ bậc $0$ đến $M - 1$ (nếu $M = 0$, in ra một dòng trống hoặc
0? Quy ước: nếu $M = 0$, in ra0).
Ví dụ
| Input | Output |
|---|---|
| 3 1 1 2 3 4 1 2 |
249561089 499122177 2 748683265 |
| 2 2 5 6 7 1 2 1 |
7 998244351 998244345 |
Giới hạn
- $0 \le M \le N \le 10^5$
Community Discussion