Self-Produced Sequences

Research note: I checked the official statement and the official Codeforces editorial/code. The official F tutorial text was not filled in, but the official solution code matches the formula derived below. No source text is copied.

Classification

Let $b$ be a chosen subsequence. All elements are nonnegative, which is the whole game here.

If the total sum of $b$ is $0$, then every chosen element is $0$, and every position is valid. This also includes the empty subsequence. The samples force this: for [0, 0], the answer is $4$, not $3$.

Now suppose $b$ contains at least one positive element. Consider a selected zero. For it to be valid, either the sum on the left is $0$, or the sum on the right is $0$. Since all numbers are nonnegative, this means either all elements to its left are zero, or all elements to its right are zero. So zeros cannot appear between positive elements. They may only form a prefix and/or suffix.

After deleting those leading and trailing zeros, we get a positive block $c_1,c_2,\dots,c_m$ where every $c_i>0$.

For the first positive element, the left sum is $0$, so it must use the right condition:

$c_1 = c_2 + c_3 + ... + c_m$.

If $T$ is the sum of the positive block, then $T=2c_1$.

Similarly, the last positive element has right sum $0$, so it must use the left condition:

$c_m = c_1 + c_2 + ... + c_{m-1}$,

so $T=2c_m$.

Therefore $c_1=c_m=T/2$.

If $m=1$, the single positive element would need to equal $0$ on one side, impossible. If $m\ge 3$, then the middle elements sum to

$T-c_1-c_m = T - T/2 - T/2 = 0$,

but all middle elements are positive. Also impossible. So the only possible positive block has length $2$, and it must be $x,x$.

So every valid subsequence is exactly one of these two forms:

• all selected elements are zero;
• $0^p, x, x, 0^q$ for some $x>0$.

That is the key observation. Everything else is just counting without stepping on a rake.

Counting

Let $z$ be the total number of zeros in the array.

All-zero subsequences: choose any subset of zero indices, so this contributes

$2^z$.

Now count subsequences of the form $0^p,x,x,0^q$. Pick two equal nonzero values at indices $i<j$ with $a_i=a_j=x$.

For this pair to be the two positive elements:

• we may choose any zero before index $i$;
• we may choose any zero after index $j$;
• we may not choose zeros between $i$ and $j$;
• we may not choose any other nonzero elements.

Let $pref(i)$ be the number of zeros before index $i$. Since $a_j$ is nonzero, the number of zeros after $j$ is $z-pref(j)$.

So this pair contributes

$2^{pref(i)} * 2^{z-pref(j)}$.

Efficient Summation

Scan the array left to right. For every value $x>0$, maintain

$sum[x] = \sum 2^{pref(i)}$

over earlier positions $i$ where $a_i=x$.

When we are at a current nonzero position $j$ with value $x$, all earlier equal positions can pair with it, so add

$sum[x] * 2^{z-pref(j)}$

to the answer.

Then insert the current position as a possible first positive element:

$sum[x] += 2^{pref(j)}$.

Zeros just increment the current prefix-zero count.

Correctness Proof

We proved every valid subsequence is either all zeros or has the exact shape $0^p,x,x,0^q$ with $x>0$.

For all-zero subsequences, choosing any subset of zero indices gives a valid subsequence, and every all-zero valid subsequence is counted once by $2^z$.

For nonzero valid subsequences, the two positive elements uniquely determine a pair of equal nonzero indices $i<j$. Once that pair is fixed, the only free choices are zeros before $i$ and zeros after $j$. There are exactly $2^{pref(i)} * 2^{z-pref(j)}$ such choices. These choices are all valid by direct checking: prefix zeros have left sum $0$, the first $x$ sees the second $x$ on the right, the second $x$ sees the first $x$ on the left, and suffix zeros have right sum $0$.

No subsequence is double-counted, because every nonzero valid subsequence has exactly two positive elements, hence exactly one such pair. Done.

Complexity

For each test case, sorting/compressing the nonzero values costs $O(n \log n)$, and the scan costs $O(n \log n)$ due to binary searches. Memory is $O(n)$.

The total $n$ over all test cases is at most $2\cdot 10^5$, so this easily fits.