Cho 3 dãy N số nguyên A1, A2, ..., An, B1, B2, ..., Bn và C1, C2, ..., Cn. Hãy đếm số bộ 3 (Ai,Bj,Ck) thỏa mãn Ai + Bj = Ck.
Input
- Dòng đầu ghi số N. ( N <= 105 )- Dòng thứ 2 ghi N số nguyên có giá trị tuyệt đối không vượt quá 50000 thể hiện dãy A.
- Dòng thứ 3 và thứ 4 lần lượt ghi dãy B và C theo quy cách tương tự.
Output
- Số bộ 3 thỏa mãn.Example
Input: 3 -1 1 1 -1 2 3 2 3 -2 Output: 4
Thời gian chạy: | 0.25s |
Giới hạn mã nguồn: | 50000B |
Memory limit: | 1536MB |
Thuật toán
- Nhận xét: Cho 2 đa thức và , tính đa thức . Nghĩa là tìm các hệ số của đa thức (Do có bậc nên có bậc lớn nhất là ).Công thức của các hệ số là
trong đó nếu ta đặt . Như vậy, để tính tất cả các hệ số của đa thức bằng công thức trên ta cần phép tính. Tuy nhiên, ta có thể tính các hệ số của đa thức chỉ với độ phức tạp bằng phép biến đổi Fourier nhanh (Fast Fourier Transform – FFT). (tham khảo)
- Bây giờ ta biểu diễn dãy số a[i] thành dạng đa thức có bậc:
ví dụ: A={1,2,3} thành $ \color{green} f(x)=x^1+x^2+x^3 $
hoặc: B={2,3,3,4} thành g(x)=x^2+2x^3+x^4 ....
Khi nhân f(x) với g(x) ta quan tâm đến số mũ. Đó chính là tổng $ \color{green} Ai+Bj$.
Mã nguồn:
- ideone.com- github.com
0 nhận xét :
Đăng nhận xét