Editorial : XOR-factorization

This editorial matches the construction in model_sol.cpp (tourist): odd $k$ outputs $k$ copies of $n$; even $k$ perturbs an all-$n$ array bitwise so the XOR becomes $n$ while keeping total sum $(k-1)n$. A simpler equivalent output is $k-1$ copies of $n$ and one $0$.

Goal

Fix $n$ and $k$. Choose $a_1,\ldots,a_k$ with $0 \le a_i \le n$ such that

$$ a_1 \oplus a_2 \oplus \cdots \oplus a_k = n, $$

and maximize $a_1 + \cdots + a_k$.

Upper bound

Always $\sum_i a_i \le kn$ because each term is at most $n$.

Case 1: $k$ odd

Start with $a_i = n$ for all $i$. Then

$$ a_1 \oplus \cdots \oplus a_k = n, $$

because $n \oplus n = 0$ and an odd number of copies of $n$ XORs down to $n$. The sum equals $kn$, meeting the upper bound. Done.

The program takes this branch whenever k % 2 == 1: it fills the answer vector with n and skips the corrective loop.

Case 2: $k$ even

Why all-$n$ fails

If every $a_i = n$, then $k$ is even implies

$$ a_1 \oplus \cdots \oplus a_k = 0, $$

but you need XOR equal to $n$, so all-$n$ is invalid unless $n = 0$ (ruled out by constraints).

Achievable optimum $(k-1)n$

Take $a_1 = \cdots = a_{k-1} = n$ and $a_k = 0$. The XOR is

$$ \underbrace{n \oplus \cdots \oplus n}_{k-1\text{ times}} \oplus 0. $$

Here $k-1$ is odd, so the XOR of the first $k-1$ terms is $n$, and the total XOR is $n$. The sum is $(k-1)n$, and every term except one is already $n$, so no coordinate can be increased without breaking $a_i \le n$ elsewhere.

Relation to the reference implementation

The code initializes every entry to n when $k$ is even (sum $kn$, XOR $0$). It then scans bits from high to low:

For a bit position where $n$ has a $1$, it toggles that bit on successive entries (advancing ptr), or only on a[0] once ptr == k. Toggling removes a set bit from an entry that started at n, which lowers the numeric value and reduces the sum.
For a bit position where $n$ has a $0$, it optionally toggles that bit on pairs of indices among the prefix built so far. XOR-toggling the same bit on two entries changes the multiset XOR by that bit twice, i.e. not at all, while adjusting how the deficit is split between coordinates.

The net effect is the same as “drop exactly $n$ from the total sum compared to all-$n$”: final sum $(k-1)n$, XOR $n$. The statement samples illustrate two valid shapes:

$n = 5$, $k = 4$: output 1 4 5 5 (same sum $15$ as three $5$s and a $0$).
$n = 4$, $k = 3$: odd $k$, so three $4$s.

Complexity

$O(k)$ work per test case for the simple construction; the bitwise loop is $O(k \log n)$ with a small constant (fixed bit range). Summed $k$ across tests is at most $10^5$, so this easily fits limits.