Nhân Đa Thức Modulo NTT
Points
20
AC Rate
0.0%
Time limit
2.0 s
Memory limit
256M
Group
number
Đề 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$
Community Discussion