问题1590--异或粽子

1590: 异或粽子

时间限制: 2 Sec  内存限制: 1024 MB
提交: 11  解决: 4
[状态] [讨论版] [提交] [命题人:]
题目描述
    小粽是一个喜欢吃粽子的好孩子。今天她在家里自己做起了粽子。 
    小粽面前有 n种互不相同的粽子馅儿,小粽将它们摆放为了一排,并从左至右编号为 1 到 n。第 i 种馅儿具有一个非负整数的属性值 ai。每种馅儿的数量都足够多,即小粽不会因为缺少原料而做不出想要的粽子。小粽准备用这些馅儿来做出 k个粽子。
     小粽的做法是:选两个整数数 l,r,满足 1≤l≤r≤n,将编号在 [l,r] 范围内的所有馅儿混合做成一个粽子,所得的粽子的美味度为这些粽子的属性值的异或和。(异或就是我们常说的 xor运算,即 C/C++ 中的 ^ 运算符) 
    小粽想品尝不同口味的粽子,因此它不希望用同样的馅儿的集合做出一个以上的粽子。 
    小粽希望她做出的所有粽子的美味度之和最大。请你帮她求出这个值吧!
输入
    从标准输入读入数据。 第一行两个正整数 n,k,表示馅儿的数量,以及小粽打算做出的粽子的数量。 接下来一行为 n个非负整数,第 i 个数为 ai , 表示第 i 个粽子的属性值。
    对于所有的输入数据都满足:1≤n≤5×105,1≤k≤min{n(n−1)/2,2×105},0≤ai≤4,294,967,295。

输出
    输出到标准输出。 输出一行一个整数,表示小粽可以做出的粽子的美味度之和的最大值。
样例输入 Copy
3 2
1 2 3
样例输出 Copy
6
提示
小粽可以选取 [3,3],[1,2] 两个区间的馅儿做成粽子,两个粽子的美味度都为 3,和为 6。可以证明不存在比这更优的方案。

来源/分类