POST2 - A cộng B version 2

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 <= 10⁵ )
 - 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

 

Read More