P5283 [12 Provinces Joint Contest 2019] XOR Zongzi.

Xiao Zong is a good kid who likes eating zongzi. Today, she started making zongzi at home by herself. There are $n$ different kinds of zongzi fillings in front of her. She places them in a row and numbers them from left to right as $1$ to $n$. The $i$-th kind of filling has a non-negative integer attribute value $a_i$. Each kind of filling is available in unlimited quantity, so Xiao Zong will not be unable to make zongzi due to lack of ingredients. She plans to use these fillings to make $k$ zongzi. Her method is: choose two integers $l$ and $r$ such that $1 \leqslant l \leqslant r \leqslant n$, mix all fillings with indices in the range $[l, r]$ to make one zongzi. The tastiness of the resulting zongzi is the **xor sum** of the attribute values of these fillings. (Xor is the operation we usually call xor, i.e. the `ˆ` operator in C/C++ or the `xor` operator in Pascal.) Xiao Zong wants to taste different flavors, so she does not want to make more than one zongzi using the same set of fillings. She wants the sum of tastiness of all the zongzi she makes to be as large as possible. Please help her compute this value.

The first line contains two positive integers $n$ and $k$, representing the number of fillings and the number of zongzi Xiao Zong plans to make. The next line contains $n$ non-negative integers. The $i$-th number is $a_i$, representing the attribute value of the $i$-th filling. For all input data: $1 \leqslant n \leqslant 5 \times 10^5$, $1 \leqslant k \leqslant \min\left\{\frac{n(n-1)}{2},2 \times 10^{5}\right\}$, $0 \leqslant a_i \leqslant 4 294 967 295$.

Output one integer on a single line, representing the maximum possible sum of tastiness of the zongzi Xiao Zong can make.

| Test Point | $n$ | $k$ | | :---------- | :---------- | :---------- | | $1$, $2$, $3$, $4$, $5$, $6$, $7$, $8$ | $\leqslant 10^3$ | $\leqslant 10^3$ | | $9$, $10$, $11$, $12$ | $\leqslant 5 \times 10^5$ | $\leqslant 10^3$ | | $13$, $14$, $15$, $16$ | $\leqslant 10^3$ | $\leqslant 2 \times 10^5$ | | $17$, $18$, $19$, $20$ | $\leqslant 5 \times 10^5$ | $\leqslant 2 \times 10^5$ | Translated by ChatGPT 5