XOR-factorization

The tempting shortcut is: for even $k$, print $k-2$ copies of $n$ and solve only two numbers. That is false. For example, with $n=30$, $k=4$, the sequence $15,23,27,29$ has XOR $30$ and sum $94$, beating the best two-number-style construction. So yeah, that idea dies pretty fast.

Bit Counts

The sum is just the contribution of every bit. If bit $b$ is set in $c_b$ of the numbers, it contributes

$c_b \cdot 2^b$

to the total sum.

The XOR condition says only this:

• if bit $b$ of $n$ is $1$, then $c_b$ must be odd;
• if bit $b$ of $n$ is $0$, then $c_b$ must be even.

But every number must also satisfy $a_i \le n$, and that is where the real problem lives.

Odd k

If $k$ is odd, print $n$ every time.

The XOR of an odd number of copies of $n$ is $n$, and the sum is $kn$, which is the absolute maximum because every $a_i \le n$. Done. No drama.

Tight and Loose Numbers

Now assume $k$ is even.

Scan bits from high to low. For each constructed number, keep whether it is:

• tight: its already-built prefix is exactly equal to the prefix of $n$;
• loose: its prefix is already smaller than $n$.

A tight number has restrictions. If the current bit of $n$ is $0`, a tight number cannot put$1$there, or it would become larger than$n$.

A loose number is already smaller, so all lower bits are free.

What To Do On a 0-Bit

Suppose the current bit of $n$ is $0$.

All tight numbers must write $0$. If there are $L$ loose numbers, we can write $1$ in some of those loose numbers. Since the XOR bit must be $0$, the count of ones must be even.

So the best count is:

$$\begin{cases} L, & L \text{ even},\\ L-1, & L \text{ odd}. \end{cases}$$

This choice has no future downside, because it does not change which numbers are loose.

What To Do On a 1-Bit

Suppose the current bit of $n$ is $1$.

Because $k$ is even, to make the XOR bit equal to $1$, the number of ones must be odd. The largest odd count at most $k$ is $k-1$, so exactly one number should write $0$ and everyone else should write $1$.

Could writing three zeros ever help by making more numbers loose? Nope. At bit $b$, every extra pair of zeros loses $2\cdot 2^b$ from the current bit. Those two extra loose numbers can gain at most $2(2^b-1)$ from all lower bits combined, which is strictly smaller. So extra zeros are a bad trade. Don't buy that garbage.

Now, if we need exactly one zero, where should it go?

If there is a tight number, put the zero there. It becomes loose. The current bit sum is unchanged, and having more loose numbers can only help future bits. If all numbers are already loose, put the zero anywhere.

Construction

Maintain two lists of indices: tight and loose.

For each bit from high to low:

• If the bit of $n$ is $1$:
  • choose one zero index;
  • if possible, take it from tight and move it to loose;
  • set this bit in every other number.
• If the bit of $n$ is $0$:
  • let take be the largest even number not exceeding loose.size();
  • set this bit in any take loose numbers.

Every bit has exactly the maximum count of ones that can be optimal under the tight/loose restriction, and the choices greedily maximize future freedom. Therefore the resulting sequence has maximum possible sum.

Correctness Proof

For odd $k$, every output number is $n$, so each number is valid, the XOR is $n$, and the sum is $kn$, the largest possible sum. Thus it is optimal.

For even $k$, consider the high-to-low construction.

A number in tight always matches the processed prefix of $n$. A number in loose already has a smaller processed prefix than $n$. Therefore, tight numbers may only put $1$ on a current bit if $n$ also has $1$ there, while loose numbers may put either bit. This invariant proves every constructed number stays at most $n$.

On a bit where $n$ has $0$, tight numbers are forced to write $0$. Among loose numbers, the XOR requires an even number of ones, so the largest possible count is the largest even number at most the loose count. The algorithm uses exactly that many, so this bit's contribution is maximal given the current state.

On a bit where $n$ has $1$, the XOR requires an odd number of ones. Since $k$ is even, the largest possible odd count is $k-1$, meaning exactly one zero. Any additional two zeros lose $2\cdot 2^b$ immediately and can recover less than that from all lower bits, so no optimal solution uses more than one zero here. The algorithm uses exactly one zero.

When that one zero can be placed on a tight number, doing so has the same current contribution as placing it on a loose number, but it increases the loose count. More loose numbers never reduce the set of possible future assignments, so this greedy choice is optimal.

Thus every bit is handled optimally, and the produced sequence maximizes the sum while satisfying the XOR and bound constraints.

Complexity

There are only about $31$ relevant bits, and each bit may touch all $k$ numbers. The complexity is $O(k\log n)$ per test case, with total $k$ bounded by $10^5$, so this easily fits.