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

    ID: 5022 远端评测题 3500ms 1024MiB 尝试: 0 已通过: 0 难度: (无) 上传者: 标签>2019各省省选二叉堆字典树,Trie 树

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

题目描述

小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。

小粽面前有 nn 种互不相同的粽子馅儿,小粽将它们摆放为了一排,并从左至右编号为 11nn。第 ii 种馅儿具有一个非负整数的属性值 aia_i。每种馅儿的数量都足够多,即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 kk 个粽子。

小粽的做法是:选两个整数数 ll, rr,满足 1lrn1 \leqslant l \leqslant r \leqslant n,将编号在 [l,r][l, r] 范围内的所有馅儿混合做成一个粽子,所得的粽子的美味度为这些粽子的属性值的异或和。(异或就是我们常说的 xor 运算,即 C/C++ 中的 ˆ 运算符或 Pascal 中的 xor 运算符)

小粽想品尝不同口味的粽子,因此它不希望用同样的馅儿的集合做出一个以上的 粽子。

小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧!

输入格式

第一行两个正整数 nn, kk,表示馅儿的数量,以及小粽打算做出的粽子的数量。

接下来一行为 nn 个非负整数,第 ii 个数为 aia_i,表示第 ii 个粽子的属性值。 对于所有的输入数据都满足:1n5×1051 \leqslant n \leqslant 5 \times 10^5, $1 \leqslant k \leqslant \min\left\{\frac{n(n-1)}{2},2 \times 10^{5}\right\}$, 0ai42949672950 \leqslant a_i \leqslant 4 294 967 295

输出格式

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

3 2
1 2 3
6

提示

测试点 nn kk
11, 22, 33, 44, 55, 66, 77, 88 103\leqslant 10^3 103\leqslant 10^3
99, 1010, 1111, 1212 5×105\leqslant 5 \times 10^5
1313, 1414, 1515, 1616 103\leqslant 10^3 2×105\leqslant 2 \times 10^5
1717, 1818, 1919, 2020 5×105\leqslant 5 \times 10^5