\(\color{red}{\text{Spoiler Alert}_{{}_{{}^{{}^{v2.99}}}}}\)

\(\color{#008b8b}{\text{Hướng dẫn trâu}}\)

• \(1\) bộ \(4\) cạnh (\(a, b, c, d\)) là cạnh của hình thang cân nếu chúng tồn tại một cách đổi lại vị trí thứ tự của bộ trên thành \((a', b', c', d')\) thỏa

Cạnh nguyên dương: \(0 < a', b', c', d'\)

Có cặp cạnh bằng nhau: \(a' = b'\)

Tứ giác lồi và không dẹt: \(a' + b' + c' > d'\)

Lúc này hình thang có \(2\) cạnh đáy song song là \(c'\) và \(d'\). Cũng như hai cạnh bên cân nhau là \(a' = b'\)

\(\color{#008b8b}{\text{Tiếp cận trâu}}\)

• Ý tưởng: Thử từng bộ \(4\) cạnh phân biệt từ \(n\) cạnh và kiểm tra xem tồn tại cách đổi vị trí sao cho nó trở thành hình thang cân hay không

Gọi mảng \((a[]): a_1, a_2, \dots, a_n\) là mảng các cạnh

Gọi \(1 \leq i_1 < i_2 < i_3 < i_4 \leq n\) là chỉ số \(4\) cạnh được gọi

Với mỗi bộ \((a_{i_1}, a_{i_2}, a_{i_3}, a_{i_4})\) ta sẽ duyệt qua các hoán vị của bộ đó, chỉ cần một hoán vị thỏa thì bộ đó thỏa

• Kết quả bài toán là số bộ mà có thể sắp xếp thành hình thang

\(\color{#008b8b}{\text{Độ phức tạp trâu}}\)

• Số cách chọn \(k\) só trong \(n\) số là \(O(C^k_n)\)

• Số hoán vị trong \(k\) số là \(O(k!)\)

• Kiểm tra mất \(O(k)\)

• Độ phức tạp là \(O(C^k_n \times k! \times k)\), trong bài này \(k = 4\) nên có thể coi như \(O(n^4)\).

\(\color{#008b8b}{\text{Hướng dẫn tổ hợp}}\)

• Để đếm số bộ khác nhau theo tổ hợp cho đơn giản, ta sẽ chia hình làm các trường hợp riêng biệt

Với (\(6\) cặp cạnh bằng nhau, \(0\) cặp cạnh khác nhau) là hình vuông

Với (\(3\) cặp cạnh bằng nhau, \(3\) cặp cạnh khác nhau) là hình thang cân phải

Với (\(2\) cặp cạnh bằng nhau, \(4\) cặp cạnh khác nhau) là hình chữ nhật

Với (\(1\) cặp cạnh bằng nhau, \(5\) cặp cạnh khác nhau) là hình thang cần thường

• Số cách để chọn \(k\) cạnh bất kì trong \(n\) cạnh bằng nhau là: \(\large{C^k_n} = \large{\frac{n!}{k!(n-k)!}}\)

Với \(k = 1 \Rightarrow \large{C^1_n} = \large{\frac{n}{1}}\)

Với \(k = 2 \Rightarrow \large{C^2_n} = \large{\frac{n(n-1)}{2}}\)

Với \(k = 3 \Rightarrow \large{C^3_n} = \large{\frac{n(n-1)(n-2)}{6}}\)

Với \(k = 4 \Rightarrow \large{C^4_n} = \large{\frac{n(n-1)(n-2)(n-3)}{24}}\)

\(\color{#008b8b}{\text{Tổ hợp}}\)

• Nhận xét: Thay vì thử các bộ \(4\) cạnh, ta chỉ cần thử các giá trị phân biệt

Các giá trị giống nhau ta dùng tổ hợp để đếm số cách chọn thì đơn giản hơn

Và số cách chọn từ một bộ bao gồm các giá trị phân biệt đó là tích các cách chọn mỗi giá trị đó với nhau

• Để thuận tiện, ta định nghĩa việc nén mảng như sau

Gọi Hàm $f(v) = $ số lần xuất hiện của \(v\) trong \(a[]\)

Gọi \(v_1, v_2, \dots, v_k\) là giá trị phân biệt của các cạnh.

Gọi \(f_1, f_2, \dots, f_k\) là số lần xuất hiện của các giá trị đó, hay \(f_p = f(v_p)\)

• Nhận xét: Vì hình thang cân, nên hiển nhiên có ít nhất một cặp cạnh bằng nhau, nên ta không cần duyệt giá trị thứ \(4\)

Vỡi mỗi bộ ta thử xét xem giá trị thứ \(4\) là giá trị nào trong \(3\) số đã chọn

Để kiểm tra thay vì duyệt hoán vị, thì vì giờ đã nén mảng, và đếm bằng tổ hợp thì tiện hơn, nên ta sẽ xét các trương hợp riêng biệt kể trên

• Hình vuông:

Có \((0 < a = b = c = d)\)

Só cạnh chọn là \(\large{\frac{f_a(f_a-1)(f_a-2)(f_a-3)}{24}}\)

• Hình thang cân phải:

Có \((0 < a = b = c < d < a + b + c)\)

Só cạnh chọn là \(\large{\frac{f_a(f_a-1)(f_a-2)}{6}} \times f_d\)

• Hình chữ nhật:

Có \((0 < a = b < c = d)\)

Só cạnh chọn là \(\large{\frac{f_a(f_a-1)}{2}} \times \large{\frac{f_c(f_c-1)}{2}}\)

• Hình thang cân thường:

Có \((0 < a = b < c < d < a + b + c)\) hoặc \((0 < c < a = b < d < a + b + c)\) hoặc \((0 < c < d < a = b)\)

Só cạnh chọn là \(\large{\frac{f_a(f_a-1)}{2}} \times f_c \times f_d\)

\(\color{#008b8b}{\text{Tối ưu băng tiền xử lí quy hoạch động}}\)

• Nếu mình cố định hai cạnh đáy \(c, d\) thì mình chỉ cần đếm số cạnh chọn 2 cạnh \(a = b\) sao cho \(\lfloor \frac{d - c}{2} \rfloor < a = b\)

• Vì trong lúc tính toán, mình đôi lúc cần tính \(s(v) = \large{\underset{x \geq v}{\Sigma}} \Big( \frac{f_x(f_x - 1)}{2}\Big)\)

• Ta tiền xử lí trước tính được các \(s_1, s_2, \dots, s_n\) hay quy hoạch động \(s_n = s(f_n)\) và \(s_p = s_{p+1} + \frac{f_p(f_p - 1)}{2}\)

• Lúc này ta có thể tính được \(s(v) = min(v_p\ \ |\ \ v_p \geq p \cup 1 \leq p \leq n)\) băng chặt nhị phân \(O(log\ n)\) thay vì duyệt lại trong \(O(n)\)

\(\color{#008b8b}{\text{Độ phức tạp}}\)

• Gọi \(k\) là số phân tử phân biệt sau khi nén

• Nén mảng mất \(O(n\ log\ n)\) mỗi truy vấn

• Tính được \(v[], f[], s[]\) trong \(O(k)\) mỗi truy vấn

• Tính được số lượng hình vuông trong \(O(k)\) mỗi truy vấn

• Tính được số lượng hình chữ nhật trong \(O(k)\) mỗi truy vấn

• Tính được số lượng hình than cân phải trong \(O(k)\) mỗi truy vấn. (Cách cài ở dưới tính chung với hình thang cần thường mất \(O(k^2 log(k))\))

• Tính được số lượng hình than cân thường trong \(O(k^2\ log(k))\) mỗi truy vấn

• Tổng cộng một truy vấn mất \(O(n\ log\ n\ +\ k^2\ log(k))\)

• Có tất cả \(Q\) truy vấn

\(\color{green}{\text{Code tham khảo }}\): Tổ hợp, Quy hoạch động, Tiền xử lí, Toán

\(^{^{\color{purple}{\text{Độ phức tạp : }} O(q \times (n\ log\ n\ +\ k^2\ log(k)))\ \color{purple}{\text{thời gian}}\ ||\ O(n)\ \color{purple}{\text{bộ nhớ}}}}\)

#include <algorithm>
#include <iostream>
#include <vector>
#include <map>

using namespace std;

typedef long long ll;
typedef pair<int, int> ii;
const int LIM = 5e3 + 13;

#define all(v) (v).begin(), (v).end()

ll v[LIM], f[LIM], s[LIM];
ll nC2(ll v) { return v * (v - 1) / 2; }
ll nC3(ll v) { return v * (v - 1) * (v - 2) / 6; }
ll nC4(ll v) { return v * (v - 1) * (v - 2) * (v - 3) / 24; }
ll query()
{
    int n;
    cin >> n;

    map<int, int> M;
    M[0] = 0;
    while (n-->0)
    {
        int v;
        cin >> v;
        ++M[v];
    }

    vector<ii> a(all(M));
    n = a.size() - 1;

    s[n + 1] = 0;
    for (int i = n; i >= 1; --i)
    {
        v[i] = a[i].first;
        f[i] = a[i].second;
        s[i] = s[i + 1] + nC2(f[i]);
    }

    ll aaaa = 0;
    ll aaab = 0;
    ll aabb = 0;
    ll aabc = 0;
    for (int i = 1; i <= n; ++i)
    {
        aaaa += nC4(f[i]);
        aabb += nC2(f[i]) * s[i + 1];
        for (int j = 1; j < i; ++j)
        {
            int p = upper_bound(v + 1, v + n + 1, (v[i] - v[j]) / 2) - v;
            if (p > n) continue;

            aabc += f[i] * f[j] * s[p];
            if (p <= i)
            {
                aaab += f[j] * nC3(f[i]);
                aabc -= f[i] * f[j] * nC2(f[i]); 
            }

            if (p <= j)
            {
                aaab += f[i] * nC3(f[j]);
                aabc -= f[i] * f[j] * nC2(f[j]);
            }
        }
    }

    return aaaa + aaab + aabb + aabc;
}

int main()
{
    int q;
    cin >> q;

    while (q-->0) cout << query() << '\n';
    return 0;
}