#P7323. [2018年12月西安集训]xor

    ID: 7337 传统题 1000ms 256MiB 尝试: 2 已通过: 1 难度: 8 上传者: 标签>CF2400提高+/省选-异或 Trie按位贪心分治算法按位独立贡献一维前缀和

[2018年12月西安集训]xor

题目描述

给定 NN 个整数 A1,…,ANA_1,\ldots,A_N。进行 MM 次选择,每次选两个不同下标 i,ji,j,得分为 Aixor⁡AjA_i\operatorname{xor}A_j。同一无序下标对不能重复选择。

求 MM 次选择的最大总得分。

输入格式

第一行两个整数 N,MN,M。第二行 NN 个整数 A1,…,ANA_1,\ldots,A_N。

输出格式

输出一个整数,表示最大总得分除以 109+710^9+7 的余数。

样例

3 2
1 2 3
5

数据范围

  • 对于 20%20\% 的数据,N≤1000N\le1000。
  • 对于 40%40\% 的数据,NM≤500000NM\le500000。
  • 对于 70%70\% 的数据,N≤10000N\le10000。
  • 对于所有数据,N≤50000N\le50000,0≤Ai≤1090\le A_i\le10^9。本评测站另有 M≤900000000M\le900000000。

原 PDF 题面