Phép Nhân Đa Thức Siêu Tốc
Points
90
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Đề bài
Cho hai đa thức P(x) = a_0 + a_1x + ... + a_Nx^N và Q(x) = b_0 + b_1x + ... + b_Mx^M. Tính đa thức tích R(x) = P(x) * Q(x). In ra các hệ số của R(x) modulo 10^9 + 7.
Dữ liệu vào
Dòng 1: Số nguyên N (0 ≤ N ≤ 2×10^5) Dòng 2: N+1 số nguyên a_0, a_1, ..., a_N (0 ≤ a_i ≤ 10^9) Dòng 3: Số nguyên M (0 ≤ M ≤ 2×10^5) Dòng 4: M+1 số nguyên b_0, b_1, ..., b_M (0 ≤ b_i ≤ 10^9)
Dữ liệu ra
Dòng 1: Số nguyên N+M Dòng 2: N+M+1 số nguyên — hệ số của R(x) mod 10^9 + 7.
Ví dụ
| Input | Output |
|---|---|
| 2\n1 2 3\n2\n4 5 6 | 4\n4 13 28 27 18 |
Giới hạn
- 0 ≤ N, M ≤ 2×10^5
- 0 ≤ a_i, b_i ≤ 10^9
Community Discussion