Phép Nhân Đa Thức Siêu Tốc

Buổi 64 — Contest Chặng 7
Points
90
AC Rate
0.0%
Time limit
3.0 s
Memory limit
256M
Group
Uncategorized
Submissions
Đề 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
Draft saved