Koxia and Sequence (CF 1770F)

Definitions

Let's collect some terminology we will use:

• The binary representation of a nonnegative integer $x$ is the unique set of powers of $2$ that sum to $x$.
• If $a$ and $b$ are integers, we say $a$ is a submask of $b$ (sometimes written $a \subseteq b$) if the powers of $2$ in the binary representation of $a$ are also in the binary representation of $b$. For instance, $3 = 011_2$ is a submask of $7 = 111_2$ but not $5 = 101_2$.

Overview

Our high-level plan will be as follows. Since any element in a good array will be a submask of $y$, the total score will also be a submask of $y$. Therefore let's compute the total answer by counting the total contribution of each power of $2$ in the binary representation of $y$. If $2^i$ appears an odd number of times among all elements of all good arrays, then we add $2^i$ to the answer; otherwise, we add $0$.

So, for each power of $2$, we want to count the parity of the number of times it appears among all good arrays. We will need some way of representing the conditions that the sum of a good array is $x$, and that the bitwise OR of a good array is $y$. However, it turns out that this bitwise OR condition is a bit unwieldy, and it is easier to work with the relaxed constraint that the bitwise OR is simply a submask of $y$. We can recover the original constraint by using the inclusion-exclusion principle and considering all submasks of $y$.

This sounds good so far, but we still haven't dealt with the meat of the problem: counting the number of arrays whose sum is $x$ with some particular constraints. Moreover, by using inclusion-exclusion and considering each power of $2$ independently, we have forced ourselves to iterate over $O(y \log y)$ (bit, mask) pairs, so ideally, we would be able to compute this number in constant time or at least $O(\log y)$. Since we are only concerned with the parity of the number of arrays, it turns out we can compute this in $O(1)$ with the help of some number theory (Lucas' Theorem) and some clever pairing-up arguments.

Matrix Fun

We assume $n$ is odd. (As shown above, the even case is trivial.) Let $B = \begin{bmatrix} b_1 & b_2 & \dots & b_k \end{bmatrix}$ be the powers of $2$ in the binary representation of $y$. For instance, if $y = 13$, then $B = \begin{bmatrix} 2^0 & 2^1 & 2^3 \end{bmatrix}$. If $A$ is a good array, since $a_1 | a_2 | \dots | a_n = y$, $a_i$ is a submask of $y$. We can imagine "redistributing" the bits in $A$ to produce a new good array.

More precisely, given a good array $A$, let $c_i$ be the number of elements that have $b_i$ in their binary representation. Since $a_1 | a_2 | \dots | a_n = y$, and there are $n$ elements in an array, $1 \leq c_i \leq n$. Let $C = \begin{bmatrix} c_1 & c_2 & \dots & c_k \end{bmatrix}^\top$. Since $a_1 + a_2 + \dots + a_n = x$, we have $BC = c_1 b_1 + c_2 b_2 + \dots + c_k b_k = x$, and there are

ways to redistribute bits to obtain new good arrays with the same $C$ vector. Each good array corresponds to some $C$, and we can compute the total score by computing the scores of each of the $F(C)$ good arrays corresponding to $C$. If $F(C)$ is even, then since each $b_i$ appears an even number of times, the score of all $F(C)$ arrays is $0$. If $F(C)$ is odd, the score of all $F(C)$ arrays is the XOR of all $b_i$, where $c_i$ is odd.

By Lucas' Theorem, ${n \choose c_i}$ is odd if and only if $c_i$ is a submask of $n$. In order for $F(C)$ to be odd, all ${n \choose c_i}$ must be odd, so $c_i$ is a submask of $n$ for all $i$. Therefore, let's rewrite our equation $BC = x$ into a form where we are only considering solutions where $c_i$ is a submask of $n$. Let $D = \begin{bmatrix} d_1 & d_2 & \dots & d_l \end{bmatrix}^\top$ be the powers of $2$ in the binary representation of $n$ (since $n$ is odd, let's assume $d_1 = 1$ for notational convenience). Then since $c_i$ is a submask of $n$, we can represent $c_i$ with the row vector $E_i = \begin{bmatrix} e_{i, 1} & e_{i, 2} & \dots & e_{i, l} \end{bmatrix}$, where $e_{i, j} \in \{0, 1\}$ and $c_i = E_i D$. Let $E$ be the matrix of all $E_i$, so

Then

Each possible binary matrix $E$ corresponds to a choice of $C$ where each $c_i$ is a submask of $n$. Let's call matrix $E$ valid if $BED = x$. For each valid matrix where each row in $E$ has a nonzero entry (i.e., $c_i \geq 1$), we add $b_i$ to the XOR-sum for each $i$ such that $e_{i, 1} = 1$ (i.e., $c_i$ is odd).

Inclusion-Exclusion

Let's compute the total score by computing the contribution of each $b_i$. We will add $b_i$ to our total score exactly when there is an odd number of valid matrices $E$ with $e_{i, 1} = 1$. However, recall that $E$ needs to satisfy the bitwise OR condition as well: for each $c_i$, we must have $c_i \geq 1$, which means that for each $i$, at least one $e_{i, j}$ in the $i$'th row must be $1$. The problem is that this is a difficult constraint to work with; we've already used this binary matrix representation to encode the constraint that each $c_i$ must be a submask of $n$, but it's harder to force each row to have a nonzero element.

Let's work around this problem by relaxing this constraint, and then recovering the original answer using the inclusion-exclusion principle over all submasks of $y$. More precisely, suppose $y'$ is a submask of $y$. Let $g(i, y')$ be the parity of the number of matrices $E$ where $e_{i, 1} = 1$ and the $k$'th row in $E$ is allowed to have nonzero entries only when $d_k$ is in the binary representation of $y'$. Importantly, we don't require here that $c_i \geq 1$. Then $g(i, y') = \bigoplus_{y' \subseteq y} g(i, y')$. This is the same idea as regular inclusion-exclusion, except we don't have to worry about signs since we only care about parity.

So now all we have to do is solve this relaxed problem for each $i$ and each submask $y'$. The issue is that there are $O(y)$ submasks and $O(\log y)$ powers of $2$ to handle, so we're already up to $O(y \log y)$ complexity, and we still haven't dealt with how to count the number of solutions to this very large subset sum problem. However, keep in mind that we are only interested in the parity of the number of solutions, and this is again where symmetry comes into play.

Consider some valid matrix $E$. For each nonzero entry $e_{i, j}$, we can think of $e_{i, j}$ as "selecting" a pair of terms $b_i d_j$ to sum to $x$. Instead of thinking of our solution space as all possible binary matrices $E$, let's think of it as multisets of terms of the form $b_i d_j$, where we select some subset to sum to $x$. Then it turns out we have a simple condition to determine the parity of the number of ways to sum to $x$:

Lemma. Let $T$ be a multiset of powers of $2$ whose sum is $S$. The number of ways to select a subset of $T$ to sum to $x$ is odd if and only if $x$ is a submask of $S$.

Proof. Suppose we have two equal numbers in our multiset; let's call them $a$ and $b$. If we have a subset that includes $a$ but not $b$, we can pair it up with a nearly identical subset that includes $b$ but not $a$, and these two subsets have the same sum. Thus if we have two equal numbers in our multiset, we only have to count the number of solutions where we either include both of them or ignore both of them, since by this pairing argument, the number of solutions where we include just one of them is even. However, if we are always either including or ignoring two terms equal to some power $2^k$, we might as well replace them with the single term $2^{k+1}$.

More precisely, if our multiset is $T$, there is a bijection between

$$\begin{aligned} \{ \text{subsets of $T$ that both either include or exclude $a$ and $b$} \} \\ \end{aligned}$$

and

$$\begin{aligned} \{\text{subsets of $T \setminus \{2^k, 2^k\} \cup \{2^{k+1}\}$} \}. \end{aligned}$$

Note that these two multisets maintain the same sum.

Moreover, we can repeat this process of replacing two copies of $2^k$ with $2^{k+1}$ until we have no more duplicate numbers in our multiset. At the end of this process, we have some set $T'$ of unique powers of $2$ whose sum is still $S$, which either has a unique subset whose sum is $x$, or there are no subsets that sum to $x$. We can form a sum of $x$ exactly when $x$ is a submask of $S$. $\square$

Let's apply this observation to solve our subproblem. Given $i$ and a submask $y'$, our multiset $T$ is the set of terms $\{ b_i d_j, 1 \leq i \leq k, 1 \leq j \leq l, b_i \in y' \}$ (which are all powers of $2$ since $b_i$ and $d_j$ are powers of $2$), where $b_i$ is in the binary representation of $y'$. Since $\sum d_j = n$, $T$ has sum $ny'$. We can assume that $e_{i, 1} = 1$, so let's take this out of our multiset, so now our multiset is $T' = T \setminus \{b_i\}$ with sum $ny' - b_i$. By our lemma, we have an odd number of solutions if and only if $x - b_i$ is a submask of $ny' - b_i$.

Putting it all together

To summarize:

• Count the contribution of each bit independently.
• Use inclusion-exclusion to sum over all submasks of $y$.
• We can solve this relaxed subproblem by checking if $x - b_i$ is a submask of $ny' - b_i$.

Despite some of the elaborate reasoning required, the resulting implementation is remarkably simple. I'll leave my submission here for reference.