XOR, Expression and Two Binary Numbers

Turn the expression sideways

Trying to generate $2^k+1$ binary strings is how you speedrun TLE. The sequence can have over $10^9$ elements, so we need to count structurally.

For a fixed generated number $a_i$, let $x_i$ be its number of ones and $y_i$ its number of zeros. Then

$$x_i y_i$$

is the number of unordered pairs of bit positions whose values are different in $a_i$: choose one position containing $1$ and one containing $0$.

Therefore,

$$\sum_i x_i y_i = \sum_i \sum_{1\le p<q\le n} [\text{bit }p\text{ differs from bit }q\text{ in }a_i] = \sum_{1\le p<q\le n} D(p,q),$$

where $D(p,q)$ is the number of sequence indices where bit columns $p$ and $q$ differ.

So we just need to understand pairs of bit columns.

XOR linearity saves the day

Consider two bit positions $p,q$. Let their one-bit sequences be generated independently. Define their difference sequence

$$d_i = b^{(p)}_i \oplus b^{(q)}_i.$$

If a midpoint is filled from endpoints $L,R$, then

$$\begin{aligned} d_{mid} &=(b^{(p)}_L\oplus b^{(p)}_R)\oplus(b^{(q)}_L\oplus b^{(q)}_R)\\ &=(b^{(p)}_L\oplus b^{(q)}_L)\oplus(b^{(p)}_R\oplus b^{(q)}_R)\\ &=d_L\oplus d_R. \end{aligned}$$

So the difference sequence is generated by the same process, starting from endpoint bits

$$(s_p\oplus s_q,\ z_p\oplus z_q).$$

Thus $D(p,q)$ is just the number of ones in a one-bit generated sequence with one of four endpoint types:

$$00,01,10,11.$$

Counting ones for one-bit endpoints

Let $W_k(u,v)$ be the number of ones after $k$ steps when the left endpoint is $u$ and the right endpoint is $v$.

For convenience define $k=0$ as the sequence containing only the two endpoints:

$$W_0(u,v)=u+v.$$

For $k\ge 1$, the first midpoint is

$$m=u\oplus v.$$

Then the left half is generated from $(u,m)$ for $k-1$ more steps, and the right half from $(m,v)$ for $k-1$ more steps. The midpoint is counted in both halves, so subtract it once:

$$W_k(u,v)=W_{k-1}(u,u\oplus v)+W_{k-1}(u\oplus v,v)-(u\oplus v).$$

Clearly

$$W_k(0,0)=0.$$

By symmetry, define

$$A_k=W_k(0,1)=W_k(1,0),\qquad B_k=W_k(1,1).$$

Base values:

$$A_0=1,\qquad B_0=2.$$

The recurrence becomes

$$A_k=A_{k-1}+B_{k-1}-1,$$

because $(0,1)$ splits into $(0,1)$ and $(1,1)$, and the shared midpoint is $1$.

Also,

$$B_k=2A_{k-1},$$

because $(1,1)$ splits into $(1,0)$ and $(0,1)$, and the shared midpoint is $0$.

Since $k\le 30$, iterating this recurrence is trivial.

Final counting

Classify every bit position by its pair of endpoint bits:

$$t = 2\cdot s_j + z_j.$$

So $t\in\{0,1,2,3\}$ represents $00,01,10,11$. Let $c_t$ be the number of columns of type $t$.

For two column types $t,u$, their endpoint-difference type is simply

$$t\oplus u.$$

Let

$$w_0=0,\qquad w_1=A_k,\qquad w_2=A_k,\qquad w_3=B_k.$$

Then the answer is

$$\sum_{0\le t\le u<4} \text{ways}(t,u)\cdot w_{t\oplus u},$$

where

$$\text{ways}(t,u)= \begin{cases} \binom{c_t}{2}, & t=u,\\ c_t c_u, & t<u. \end{cases}$$

When $t=u$, the contribution is actually zero because $t\oplus t=0$, but keeping the uniform formula is harmless.

Correctness proof

Lemma 1. For every sequence index $i$, $x_i y_i$ equals the number of unordered pairs of bit positions that differ in $a_i$.

Proof. A differing pair consists of one bit equal to $1$ and one bit equal to $0$. There are $x_i$ choices for the one-bit and $y_i$ choices for the zero-bit, hence $x_i y_i$ pairs. $\square$

Lemma 2. For any two bit positions $p,q$, their XOR/difference sequence is generated by the same process from endpoints $(s_p\oplus s_q, z_p\oplus z_q)$.

Proof. Initially this is true at the two endpoints. If it is true before a step, then for any newly filled midpoint between endpoints $L,R$,

$$(b^{(p)}_L\oplus b^{(p)}_R)\oplus(b^{(q)}_L\oplus b^{(q)}_R) = (b^{(p)}_L\oplus b^{(q)}_L)\oplus(b^{(p)}_R\oplus b^{(q)}_R).$$

That is exactly the XOR of the two endpoint values in the difference sequence, so the process matches. $\square$

Lemma 3. The recurrence for $A_k$ and $B_k$ correctly computes the number of ones in every one-bit endpoint case.

Proof. The case $00$ stays all zero. For any endpoints $(u,v)$, the first midpoint is $u\oplus v$, then the left and right halves are recursively generated with $k-1$ steps and share that midpoint. This gives

$$W_k(u,v)=W_{k-1}(u,u\oplus v)+W_{k-1}(u\oplus v,v)-(u\oplus v).$$

Substituting $(0,1)$ gives $A_k=A_{k-1}+B_{k-1}-1$, and substituting $(1,1)$ gives $B_k=2A_{k-1}$. $\square$

Theorem. The algorithm outputs the required expression.

Proof. By Lemma 1, the expression equals the sum over all unordered pairs of bit columns of the number of indices where they differ. By Lemma 2, for a pair of endpoint types $t,u$, this number is $W_k(t\oplus u)$. By Lemma 3, the algorithm computes all needed $W_k$ values correctly. The final summation counts every unordered pair of bit columns exactly once, grouped by endpoint type. Therefore the computed value is exactly the required expression. $\square$

Complexity

For each test case, we do $O(k)$ recurrence work and scan the strings once:

$$O(n+k)$$

time and

$$O(1)$$

extra memory. Since $\sum n\le 10^5$ and $k\le 30$, this is comfortably fast. Use long long; the answer fits in signed 64-bit.