Hello, Codeforces community! Today, I want to share my solution to a problem from recent contest: Binary Subsequence Value Sum. Rather than using polynomials and FFT, I tried to approach this problem from a different viewpoint — probability! Now, let's get started with the solution itself.

1. Deterministic definition of the score

Suppose you have a binary string $$$v$$$ of length $$$m$$$. Interpret each character as a “contribution”: assign $$$+1$$$ for a ‘1’ and $$$-1$$$ for a ‘0’. Define

so that $$$d$$$ is the overall “imbalance” of $$$v$$$.

The score of $$$v$$$ is defined as

where $$$F(v,1,i)$$$ is imbalance of prefix and $$$F(v,i+1,m)$$$ is imbalance of suffix; if the prefix imbalance is $$$S$$$, then the suffix is $$$d-S$$$, and the product is

For fixed $$$d$$$, the product $$$S(d-S)$$$ is a quadratic function in $$$S$$$. It is maximized when

However, since $$$S$$$ must be an integer (and may not be exactly $$$d/2$$$ when $$$d$$$ is odd), the best we can do is to take

Thus the maximum product is

So in one compact expression, the score of $$$v$$$ can be written as

2. Counting scores over all subsequences

Now, consider a fixed binary string $$$s$$$ of length $$$n$$$ with $$$R$$$ ones and $$$Z = n-R$$$ zeros.

A nonempty subsequence of $$$s$$$ is obtained by choosing, independently for each position, whether to include that bit. (There are $$$2^n$$$ subsequences in total, including the empty one—but the empty subsequence contributes nothing to the score.)

Imagine that for each bit in $$$s$$$ we make an independent choice with probability $$$1/2$$$ of including it. Then every subsequence occurs with equal probability $$$(\frac{1}{2})^n$$$.

For any subsequence $$$v$$$, let its imbalance be

Then the score of that subsequence is, by our previous argument,

We want to sum the scores over all nonempty subsequences. Rather than summing directly, we use the idea of expectation.

Recall that for any function $$$f(v)$$$ defined on the set of subsequences (with the uniform probability distribution), the average value is:

Multiplying by $$$2^n$$$ recovers the sum over all subsequences:

3. Calculating the Expectation $$$E[(d')^2]$$$

For each bit of $$$s$$$, define a random variable $$$X_i$$$ as follows:

• If the $$$i$$$th bit is a ‘1’ and is chosen, $$$X_i=+1$$$; if it’s not chosen, $$$X_i=0$$$.
• If the $$$i$$$th bit is a ‘0’ and is chosen, $$$X_i=-1$$$; if it’s not chosen, $$$X_i=0$$$.

Then the imbalance for a given subsequence is

• For ‘1’: $$$E[X_i]= \frac{1}{2}$$$ (since it contributes $$$+1$$$ with probability $$$1/2$$$).
• For ‘0’: $$$E[X_i]= -\frac{1}{2}$$$.

Thus, if there are $$$R$$$ ones and $$$Z$$$ zeros,

Each $$$X_i$$$ is a Bernoulli-type variable with two outcomes (nonzero with probability $$$1/2$$$ and zero with probability $$$1/2$$$). In either case (for ‘1’ or ‘0’), one can show that

Since the choices are independent,

Recall that

Thus,

Then the expected value of $$$\frac{(d')^2}{4}$$$ is

So if we (naively) approximated the score of every subsequence by $$$\frac{(d')^2}{4}$$$, then the total over all $$$2^n$$$ subsequences would be:

4. $$$d'$$$ parity correction

The true score of a subsequence with imbalance $$$d'$$$ is

which means that whenever $$$d'$$$ is odd, our naive expression $$$\frac{(d')^2}{4}$$$ is an overestimate by $$$\frac{1}{4}$$$.

A classical combinatorial fact (which one may also derive via the bruteforce check, as I did) is that the total number of subsequences with an odd imbalance is exactly half of all subsequences. Thus, the total “overcount” when summing $$$\frac{(d')^2}{4}$$$ is:

Therefore, by linearity of expectation, the correct total sum $$$S$$$ over all nonempty subsequences is:

Substitute the expectation we computed:

5. Simplifying to the Final Formula

Factor $$$2^{n-4}$$$ out of both terms, and we obtain the final closed-form formula:

My solution: 309852412. Thank you for reading!