### lizhiqing's blog

By lizhiqing, history, 4 months ago, I recently came across a question that I thought about for a long time without any ideas. I read its solution, but I still didn't understand how to do it.

I've put the problem and part of the solution below in the hope that someone can answer my question.

Given integers $n,l,r,x$, find an integer sequence $a_1 \ldots a_n$ such that $a_i \in [l,r]$, and the XOR sum is $x$. Maximize $\sum_{i=1}^n a_i$. If there is a solution, output the largest possible $\sum_{i=1}^n a_i$. If there is no solution, output -1.

Multiple test cases. $1 \leq n \leq 10^9$, $0 \leq x,l,r \leq 10^9$, $T \leq 10^6$.

And there are some lemmas in the solution,but I can't prove it.

#### Lemma:

1. If a solution exists, there are at most $\lceil\log_{2}{r}\rceil$ numbers $a_i$ which satisfy $a_i < r$;

2. If a solution exists and the highest differing bit position between $l$ and $r$ is $t$, then in the optimal solution there are at most $3$ numbers $a_i$ which are less than $2^t$. math, Comments (0)