Biến đổi Fourier nhanh (FFT): Nhân hai đa thức bậc cao trong O(N log N)
Cho hai đa thức A(x) có bậc N và B(x) có bậc M:
Tiến độ của tôi ở bài này
Điểm được lưu vào tài khoản sau khi chấm bài.
Đang tải điểm của bạn…
Kiến thức và chủ đề
Kiến thức tiên quyết: complex-numbers, divide-and-conquer, recursion.
Nội dung đề bài
Mô tả bài toán
Cho hai đa thức A(x) có bậc N và B(x) có bậc M: A(x) = a0 + a1 x + a2 x2 + … + aN xN B(x) = b0 + b1 x + b2 x2 + … + bM xM
Yêu cầu: Tính tích C(x) = A(x) × B(x): C(x) = c0 + c1 x + c2 x2 + … + cN+M xN+M sử dụng thuật toán Biến đổi Fourier nhanh (Fast Fourier Transform - FFT) trong thời gian O((N + M) log(N + M)).
Dữ liệu vào
- Dòng đầu chứa hai số nguyên N, M (0 ≤ N, M ≤ 100,000).
- Dòng thứ hai chứa N + 1 số nguyên a0, a1, …, aN (-1000 ≤ ai ≤ 1000).
- Dòng thứ ba chứa M + 1 số nguyên b0, b1, …, bM (-1000 ≤ bi ≤ 1000).
Dữ liệu ra
- In ra N + M + 1 số nguyên c0, c1, …, cN+M trên một dòng, cách nhau bởi dấu cách.
Quy ước nộp bài
- Chỉ cần viết một chương trình đọc
stdinvà in rastdout. Bài này không yêu cầu viết hàm. - Không dùng
coutđể in lời nhắc trước khi đọc dữ liệu. Lời nhắc sẽ lọt vàostdoutvà làm bài sai. - Chỉ in đúng nội dung ở mục Output. Không in thêm nhãn, dòng trống hay ký tự thừa.
- Output được so khớp từng ký tự, phân biệt chữ hoa/thường và dấu câu.
Input
- Các tham số truyền vào hàm/lớp solution hoặc dữ liệu đầu vào theo định dạng mô tả.
Output
- Kết quả trả về của hàm/lớp solution hoặc dữ liệu in ra màn hình theo đúng đặc tả.
Ràng buộc
- Thời gian chạy tối đa: 1500ms.
- Giới hạn bộ nhớ: 256MB.
- Dữ liệu đầu vào tuân thủ đúng định dạng và miền giá trị được mô tả.
Ví dụ 1
Input
Input:
2 2
1 2 3
4 5 6
Output:
4 13 28 27 18Output
Thành công / Đáp ứng đầy đủ ràng buộcGiải thích
Dữ liệu kiểm thử mẫu và kết quả thực thi theo yêu cầu.
Gợi ý và lời giải chỉ mở sau khi bạn bấm Nộp bài. Giáo viên và quản trị viên mở được ngay.
Góp ý & báo lỗi bài tập
Đề bài chưa rõ, test có vấn đề hay bạn có ý tưởng giúp bài tốt hơn? Gửi cho đội ngũ AI Empire nhé — mỗi góp ý đều được đọc.