Subtask 1. ~n \le 40~

Duyệt mọi bộ bốn và tính kết quả.

Độ phức tạp: ~O~ (~n^4~).

Subtask 2. ~n \le 400~.

Ta chỉ duyệt ~i < j < p~, sau đó, ta cần đếm số lượng giá trị ~x~ sao cho ~a_i - a_j = a_p - x~, hay ~x = a_p - a_i + a_j~.

Điều này có thể thực hiện bằng một map hay mảng đánh dấu.

Về cài đặt, ta nên duyệt ~p~ trước từ ~n - 1~ về ~3~. Trước khi tiếp tục ~p--~, ta sẽ duyệt ~q~ từ ~p + 1~ tới ~n~, và tăng đánh dấu của ~a_q~ lên một. Khởi tạo trong mảng đánh dấu sẽ có một lần xuất hiện của ~a_n~.

Độ phức tạp: ~O~ (~n^3~).

Subtask 3. ~n \le 4000~.

Ta sẽ chỉ duyệt ~i~ và ~j~, sau đó đếm số lương cặp có ~a_i - a_j = a_p - a_q~ bằng mảng đánh dấu.

Đây là một kỹ thuật khá phổ biến khi ta đếm số bộ bốn chỉ số, đó là ta lặp hai chỉ số bất kỳ, sau đó sử dụng mảng đánh dấu đếm hai chỉ số còn lại.

Về thứ tự duyệt thì cũng không khác nhiều so với subtask 2.

Độ phức tạp: ~O~ (~n^2~).

Code mẫu:

#include <bits/stdc++.h>
using namespace std;

#define int long long

const int N = 1e6 + 9;
const int mod = 1;

int n, a[N];
map <int, int> ok;

signed main (){
    ios_base::sync_with_stdio (false);
    cin.tie (NULL);
    cout.tie (NULL);
    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];
    if (n <= 3){
        cout << 0; return 0;
    }
    ok[a[n - 1] - a[n]]++;
    int res = 0;
    for (int j = n - 2; j >= 2; j--){
        for (int i = j - 1; i >= 1; i--) res += ok[a[i] - a[j]];
        // cập nhật với giá trị j, do sau vòng lặp này, j trừ đi 1
        // ta sẽ có thêm một số cặp mới
        for (int k = j + 1; k <= n; k++) ok[a[j] - a[k]]++;
    }
    cout << res;
}