Mình xin chia sẻ lời giải bài toán này như sau:

• Đầu tiên ta có một chú ý sau, một tam giác là tam giác cân khi và chỉ khi các cạnh của nó có dạng như sau \((a,a,b)\) với điều kiện \(a+a>b\) (Ta không cần xét \(a+b>a\) (vì điều này hiển nhiên đúng)) và ở đây \(b\) có thể bằng \(a\).
• Do đó bài toán trên quy về đếm số bộ \((a,a,b)\) thỏa mãn \(a+a>b\) (hay \(b<=2 * a-1\))
• Mình sẽ minh họa cách làm của mình thông qua một bài toán cụ thể, và từ đó ta tổng quát lên cho bài toán gốc như sau:
• Giả sử ta có mảng a gồm 6 phần tử sau: \(\text{4 5 4 6 4 7}\)
• Để dễ dàng cho việc đếm, ta có thể sắp xếp (tăng dần) lại các phần tử như sau: \(\text{4 4 4 5 6 7}\)
• Ta nhận thấy rằng, khi sắp xếp lại như vậy, kết quả của bài toán không bị ảnh hưởng (vì ta chọn 3 phần từ bất kỳ không trùng nhau từng đôi một thì nó luôn tồn tại thứ tự chỉ số thỏa mãn \(i<j<k\)). Do đó kết quả của bài toán sẽ không bị ảnh hưởng khi ta sắp xếp lại các phần tử, nhưng nó sẽ đem đến cho ta một cái lợi đó là ta thấy rằng, những phần tử bằng nhau sẽ đứng kề nhau.
• Tiếp theo ta sẽ phân hoạch mảng này thành những tập hợp con có tính chất như sau: Những phần tử thuộc về cùng một tập thì chúng sẽ có giá trị giống nhau. Cụ thể như sau, ta gọi \(d[i]\) là tập hợp các phần tử chứa giá trị \(i\) trong mảng đã cho.
• Khi đó từ ví dụ ta có: \(|d[4]|=3,|d[5]|=1,|d[6]|=1,|d[7]|=1\). (Ghi chú: \(|X|\) là số phần tử của tập \(X\)).
• Vậy, việc phân hoạch này có ý nghĩa gì ?
• Đó là nó sẽ giúp ta đếm mà không bị trùng lặp, và việc đếm trở nên rõ ràng, mạch lạc.
• Khi đó ta dễ dàng ta đếm được số bộ tam giác cân như sau: \(\binom{3}{2} * 3+\binom{3}{3}\) (Ghi chú: \(\binom{n}{k}=\frac{n!}{k!(n-k)!}\))
• Mình sẽ giải thích cụ thể vì sao lại có công thức đó:
• Đầu tiên: Mình sẽ đếm số bộ tam giác cân (khác đều) như sau: Ta sẽ chọn \(2\) phần tử bất kì từ tập \(d[4]\) và \(1\) phần tử bất kì không thuộc tập \(d[4]\) thỏa mãn phần tử đó phải bé hơn \(2 * 4\). Khi đó ta có: \(\binom{3}{2} * 3\) cách.
• Tiếp theo, mình sẽ đếm số bộ tam giác đều: Vì chỉ duy nhất tập \(d[4]\) có số phần là lớn hơn hoặc bằng \(3\) nên sẽ có: \(\binom{3}{3}\) cách.

• Vậy số bộ tam giác cân cần tìm sẽ là : \(\binom{3}{2} * 3+\binom{3}{3}\) (bộ).

• Từ đây ta tổng quát lên cho một mảng \(A\) gồm \(n\) phần tử như sau:

• Gọi \(d[i]\) là số lượng phần tử \(i\) có trong mảng và \(s[i]\) là số lượng phần tử nhỏ hơn hoặc bằng \(i\) . Thì khi đó số lượng tam giác cân cần tìm là: \(\sum\limits_{i=1}^{maax}(\binom{d[i]}{2} * (s[min(2*i-1,maax)]-d[i])+\binom{d[i]}{3})\). Trong đó: \(maax=max\left\{A[i]\right\}\forall i=\overline{1,n}\)
• Và \(s[i]\) được xây dựng như sau: \(s[i]=s[i-1]+d[i]\forall i=\overline{1,maax},s[0]=0\)
• Chúng ta chú ý thêm một điều nữa: đó là \(\binom{x}{2}=\frac{x(x-1)}{2}\) và \(\binom{x}{3}=\frac{x(x-1)(x-2)}{6}\)
• Để cho tiện thì các bạn có thể dùng lũy thừa nhị phân như bên dưới để tính sẵn \(po(6,mod-2)\) và \(po(2,mod-2)\).

ll po(ll a,ll n){
  ll res=a,ans=1;
  while(n){
    if(n%2) ans=ans*res%mod;
    res = res*res%mod;
    n/=2;
  }
  return ans;
}

• Và điều chú ý cuối cùng, là để có thể vượt qua những test case 19 và 20, các bạn cần phải dùng thêm fast IO như bên dưới thì mới AC nhé!

ios_base::sync_with_stdio(false);

 cin.tie(NULL);

 cout.tie(NULL);

• Và các bạn có thể tham khảo code của mình tại \(\href{https://ideone.com/apMPJV}{đây}\)
• Ps: Bạn có thể áp dụng bài này vào bài toán Tam giác cân để giải nhé : \(\href{http://lqdoj.edu.vn/problem/tgcan}{Link}\)
• Nếu có chỗ nào khó hiểu hoặc sai thì các bạn cứ comment nhé!