Hướng dẫn

Ta có p1 p2 p3 thì

p1 bắt tay p2

p1 bắt tay p3

p2 bắt tay p3

=> Các cặp thoả mãn là (p1, p2), (p1, p3), (p2, p3)

=> Tổng các cặp thoả mãn là 3 (TTM)

Tạo công thức tính nhanh thông qua ma trận TTM nhân TTM <=> 3 nhân 3

    p1 p2 p3
p1  X  T  T
p2  X  X  T
p3  X  X  X

Trong đó:
T là thoả mãn
X là không thoả mãn

Ta thấy rằng các cặp thoả mãn là nửa tam giác trên đường chéo chính.

Đầu tiên ta n*n để tính tổng ma trận này.

Ở dòng cuối p3 thì cả dòng toàn X thế nên loại bỏ đi n*(n-1)

Ma trận còn:

    p1 p2 p3
p1  X  T  T
p2  X  X  T

Nhận ra ngay tổng các cặp thoả mãn = không thoả mãn => Chia 2

=> (n*(n-1))/2 vậy đã xong bài toán bắt tay này nhé :vv

Tổng độ phức tạp o(1)