Đếm Bộ Ba Cấp Số Cộng Theo Thứ Tự

Buổi 60 — FFT / NTT Mathematics
Points
75
AC Rate
0.0%
Time limit
1.0 s
Memory limit
256M
Group
number
Submissions
Đề bài

Cho một dãy số nguyên dương $A_1, A_2, \dots, A_N$. Một bộ ba chỉ số $(i, j, k)$ được gọi là lập thành cấp số cộng theo thứ tự nếu thỏa mãn đồng thời $1 \le i < j < k \le N$ và $A_j - A_i = A_k - A_j$ (tức là $A_i + A_k = 2 A_j$). Hãy đếm tổng số bộ ba $(i, j, k)$ như vậy trong dãy $A$.

Dữ liệu vào

Dòng đầu tiên chứa số nguyên $N$ ($3 \le N \le 20\,000$). Dòng thứ hai chứa $N$ số nguyên $A_1, A_2, \dots, A_N$ ($1 \le A_i \le 30\,000$).

Dữ liệu ra

In ra một số nguyên duy nhất là số lượng bộ ba thỏa mãn yêu cầu.

Ví dụ
Input Output
5
1 2 3 4 5
4
Giới hạn

Thời gian: 1.0s, Bộ nhớ: 256MB.

Draft saved