Chia Đa Thức Lấy Dư

Buổi 60 — FFT / NTT
Points
75
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
number
Submissions
Đề 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 ra 0).
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$
Draft saved