Background

PA 2024 5C1

Problem Description

This problem is translated from Round 5 of PA 2024, Bardzo Ulubiony Ciąg. Thanks to Macaronlin for providing the translation.

Given an integer array $a$ of length $n$, all subarray sums of $a$ form an array $b$ of length $\frac{n(n+1)}{2}$. The subarray sums are ordered by increasing starting index of the subarray; if two subarrays have the same starting index, they are ordered by increasing ending index.

For the newly formed array $b$, compute the number of triples $(i,j,k)$ such that $b_i+b_j+b_k=0\ (i<j<k)$.

Input Format

The first line contains an integer $n\ (1\le n\le 500)$, the length of array $a$.

The second line contains $n$ integers $a_1,a_2,\ldots,a_n\ (|a_i|\le 20\,000)$, representing array $a$.

Output Format

Output one integer: the number of triples $(i,j,k)$ in array $b$ satisfying $b_i+b_j+b_k=0\ (i<j<k)$.

3
7 -4 -2

1

10
0 0 0 0 0 0 0 0 0 0

26235

Hint

Sample Explanation 1

Array $b$ is $[7,3,1,-4,-6,-2]$. Only the three distinct elements $3,1,-4$ satisfy the condition, so the answer is $1$.

Sample Explanation 2

Array $b$ consists of $55$ zeros. Any choice of three indices $i<j<k$ has sum $0$, so the answer is $26235$.

Translated by ChatGPT 5