4959：[十二省联考 2019] 异或粽子

# [十二省联考 2019] 异或粽子

题目描述

小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。 小粽面前有 $n$ 种互不相同的粽子馅儿，小粽将它们摆放为了一排，并从左至右编号为 $1$ 到 $n$。第 $i$ 种馅儿具有一个非负整数的属性值 $a_i$。每种馅儿的数量都足够多，即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 $k$ 个粽子。 小粽的做法是：选两个整数数 $l$, $r$，满足 $1 \leqslant l \leqslant r \leqslant n$，将编号在 $[l, r]$ 范围内的所有馅儿混合做成一个粽子，所得的粽子的美味度为这些粽子馅儿的属性值的**异或和**。（异或就是我们常说的 xor 运算，即 C/C++ 中的 `ˆ` 运算符或 Pascal 中的 `xor` 运算符） 小粽想品尝不同口味的粽子，因此她不希望用同样的馅儿的集合做出一个以上的粽子。 小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧！

输入格式

第一行两个正整数 $n$, $k$，表示馅儿的数量，以及小粽打算做出的粽子的数量。 接下来一行为 $n$ 个非负整数，第 $i$ 个数为 $a_i$，表示第 $i$ 个粽子的属性值。 对于所有的输入数据都满足：$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$。

输出格式

输出一行一个整数，表示小粽可以做出的粽子的美味度之和的最大值。

3 2
1 2 3

6

提示

| 测试点 | $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$ | 标签: P5283|2019|各省省选|堆|可持久化|前缀和|字典树 Trie

来源

P5283|[十二省联考 2019] 异或粽子