TouchStone
  Please Login
ログイン 登録
距离明年CSP第一轮: ??天 距离CSP第二轮: ??天 距离NOIP还有: ??天
 ホームページ  問題セット  試験一覧  提出状況  掲示板  統計情報
  • ホーム
  • 問題セット
  • P5571
  • 問題
  • P5571「十二省联考 2019」异或粽子
    制限 : 時間制限 : - MS   メモリ制限 : - KB
    問題説明

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

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

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

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

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

    入力形式

    从标准输入读入数据。

    第一行两个正整数 \(n,k\),表示馅儿的数量,以及小粽打算做出的粽子的数量。

    接下来一行为 \(n\) 个非负整数,第 \(i\) 个数为 \(a_i\),表示第 \(i\) 个粽子的属性值。

    出力形式

    输出到标准输出。

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

    サンプル入力

    3 2
    1 2 3

    サンプル出力

    6

    ヒント
    测试点 \(n\) \(k\)
    $1\sim 8$ \(\le 10^{3}\) \(\le 10^{3}\)
    $9\sim 12$ \(\le 5 \times 10^{5}\) \(\le 10^{3}\)
    $13\sim 16$ \(\le 10^{3}\) \(\le 2 \times 10^{5}\)
    $17\sim 20$ \(\le 5 \times 10^{5}\) \(\le 2 \times 10^{5}\)

    对于所有的输入数据都满足:$1\le n \le 5 \times 10^{5},1\le k\le \text\lbrace\frac{n(n-1)}{2},2 \times 10^{5}\rbrace,0\le a_i \le 4,294,967,295$。