P10524 [XJTUPC 2024] Cyclic Shift

Given an array $a_i$ of length $2^n$ ($0 \leq i < 2^n$), you may perform cyclic shifts any number of times. Find the maximum values of $\sum_{i=0}^{2^n-1} a_i \oplus i$, $\sum_{i=0}^{2^n-1} a_i \& i$, and $\sum_{i=0}^{2^n-1} a_i | i$. Here, $\oplus$, $\&$, and $|$ denote bitwise XOR, bitwise AND, and bitwise OR, respectively. For an array $x_i$ of length $m$ ($0 \leq i < m$), the result after one cyclic shift is $x'_i$: $$x'_i = \left\{ \begin{array}{ll} x_{i - 1} & i \neq 0 \\ x_{m - 1} & i = 0 \end{array}\right.$$

The first line contains an integer $n$ ($1 \leq n \leq 20$), as described above. The next line contains $2^n$ integers $a_i$ ($0 \leq a_i < 2^n$), representing the given array.

Output one line with three integers separated by spaces, which are the maximum values of $\sum_{i=0}^{2^n-1} a_i \oplus i$, $\sum_{i=0}^{2^n-1} a_i \& i$, and $\sum_{i=0}^{2^n-1} a_i | i$.

Translated by ChatGPT 5