#2560异或和问题 jdfz集训

题目描述

N个数字，要求选择M次，每次从N个数中选出两个数(Ai,Aj)(但不能和之前某次选择相同)，此次选择的得分为Ai xor Aj。

求最大得分。

输入格式

第一行包含两个整数N,M

接下来一行共N个整数描述N个数字。

输出格式

输出一个整数，表示最大得分除以10^9+7的余数

解法

　　设ans为两两异或得到的数中第m大的数。

　　把N个数一起放到trie树里跑，对于ans的每一位，求出所有异或后这一位是1的数对的个数①加上已知异或结果大于ans的数对的个数②，如果>=2*m个（因为每两个数之间重复计算一次），那么这位肯定是1，否则一定是0。

①（举个例子，ans=01xxxx，a^b=011xxx,则统计。a^b=010xxx,则不统计。a^b=101xxx不统计。）

②（ans=0101xx 如果a^b=1xxxxx则统计。a^b=011xxx则统计。）

　　为了方便说明，定义“异或数”为某两个数字异或的结果。某数的第p位意思是这个数的二进制下从左往右数第p位。

　　计算ans的第K位时，ans的前K-1位是已确定的。所以计算ans第K位的方法是：从N个数里枚举一个i，然后在trie树上从高位向低位跑。如果ans的第p位是0，sum(总数)+=与i异或后第p位是1的数的个数。往异或后等于ans的第p位方向走。最后sum+=异或后第K位是1的个数。特殊地，我们需要在trie树的每个节点上储存一个size，表示以该节点为根节点的子树中所有数的个数。这样，统计与i异或后第p位是1的个数时，只需要访问size就可以O（1）计算了。　　如果sum>=2*m，那么这位肯定是1，否则一定是0。复杂度nlogn。

　　求出m大值ans后，枚举每一个数，算出和它异或>=ans的数的和。还是从高位到低位处理：如果当前第K位是1，那么只能往异或后等于1的方向走，直接递归下去。否则，我们需要把异或之后这位是1的子树统计入答案，然后往异或后等于0的方向走。如何统计答案？在建立trie树的时候对每个节点还要维护一个信息，就是以这个点为根的子树所包含的数中，每一位有多少个数是1，有多少个数是0，这样就可以在logn的时间内算出某个数和这颗子树中所有数的异或和了。然后再加上当前数和使得第i位异或为1的那个节点为根的子树的异或和就好了。

　　总体复杂度nlog^2n，但是常数小。

巴特西

#2560异或和问题 jdfz集训—秦岳

最新文章

热门文章