Nhân Đa Thức Modulo NTT

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

Cho hai đa thức $A(x)$ bậc $N$ và $B(x)$ bậc $M$. Hãy tính đa thức tích $C(x) = A(x) \cdot B(x)$ với các hệ số lấy modulo $998244353$.

Dữ liệu vào
  • Dòng đầu chứa hai số nguyên $N, M$ ($0 \le N, M \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$).
Dữ liệu ra

In ra $N + M + 1$ số nguyên là các hệ số của $C(x) \bmod 998244353$.

Ví dụ
Input Output
2 2
1 2 3
4 5 6
4 13 28 27 18
1 1
998244352 1
998244352 1
1 998244351 1
Giới hạn
  • $0 \le N, M \le 10^5$
Draft saved