本文章由 WyOJ Shojo 从洛谷专栏拉取，原发布时间为 2023-05-13 21:05:55

P5283 [十二省联考 2019] 异或粽子 加强版。

step1

首先先将 $m$ 乘二，变成统计最大的 $m$ 个有序对。

把所有 $a_i$ 插入到一个 Trie 中，对于每个结点记录子树中叶子个数，第一步先来考虑求出第 $m$ 大值是什么，记第 $m$ 大值为 $lim$。

这个可以从高位到低位按位确定。假设当前考虑完了 $[30,b+1]$ 位，正在确定第 $b$ 位，对于 Trie 上第 $b+1$ 层的每一个结点 $i$，记录另一个结点 $cor_i$ 表示 $i$ 和 $cor_i$ 对应值的异或和的 $[30,b+1]$ 位等于 $lim$。这样就能对于第 $b$ 位统计出满足异或和 $[30,b+1]$ 位和 $lim$ 相等且第 $b$ 位为 $1$ 的点对数，从而确定 $lim$ 的第 $b$ 位是 $0$ 还是 $1$。

由于 Trie 上每个结点只会被遍历一遍，这部分复杂度是 $O(n \log V)$ 的。

step2

接下来考虑统计答案，这里只统计异或和小于 $lim$ 的点对贡献，等于 $lim$ 的贡献为 $lim*(m-cnt)$，$cnt$ 为异或和小于 $lim$ 的点对数。

枚举点对异或和和第 $m$ 大值二进制表示的 lcp。具体来讲，依然枚举 Trie 树上的一个点 $i$，贡献其实就是 $i$ 的子树 $t$ 以及 $cor_i$ 的子树 $t \oplus 1$ 中任意两对值的异或和，异或和没有很好的性质，只能拆位算，记 $s_{i,j,0/1}$ 表示 $i$ 的子树中第 $j$ 位为 $0/1$ 的值的个数，然后直接枚举每一位算贡献即可。

step3

最后来分析复杂度：

首先是 $s_{i,j,0/1}$ 的计算，如果点 $i$ 两个儿子都有，那么直接 $O(\log V)$ 暴力合并，否则 $s_{i}$ 可以直接继承其仅有的一个儿子的值（可以用指针实现），这样在三度点处的贡献是 $O(\log V)$ 的，在二度点处为 $O(1)$，由于叶子个数只有 $O(n)$ 个，所以三度点也只有 $O(n)$ 个，于是这部分是 $O(n \log V)$ 的。

然后是暴力拆位算贡献的部分，每一对 $(i,cor_i)$ 会造成 $O(\log V)$ 的贡献。如果 $i,cor_i$ 中有一个是三度点，注意到 $i$ 和 $cor_i$ 是一一对应的，所以这样的 $(i,cor_i)$ 只有 $O(n)$ 个；注意到如果 $i$ 和 $cor_i$ 中如果有一个是空子树，那么是不需要贡献 $O(\log V)$ 的，而如果 $i,cor_i$ 均为二度点且有 $O(\log V)$ 的贡献的话，那么是必然不会继续从 $i$ 递归到它的子树中的，所以对于每一个叶子，其祖先中的二度点至多有 $1$ 个会有贡献，因此这样的二度点总数也是 $O(n)$ 的，于是这部分复杂度也是 $O(n \log V)$ 的。

总复杂度 $O(n \log V)$。

代码（写的很丑QwQ）：

#include <bits\/stdc++.h>
#define lowbit(x) (x & -x)
#define eb emplace_back
#define pb push_back
#define mp make_pair
#define rep for (int t = 2; t--; )
using namespace std;

#define getchar() (p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 1 << 21, stdin), p1 == p2) ? EOF : *p1++)
char buf[1 << 21], *p1 = buf, *p2 = buf;

inline int read() {
	int x = 0; char c = getchar();
	while (c < '0' || c > '9') c = getchar();
	while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	return x;
}

typedef long long ll;
const int N = 5e4+5;
const int Mod = 1e9+7;

int n, a[N], tot = 1, ans;
ll m, lim;
int bf[N * 2][2][30], c, (*s[N * 30])[30];
int cor[N * 30];
vector<int> id[31];

inline void Add(int &a, int b) { a += b; if (a >= Mod) a -= Mod; }

struct node {
	int son[2], siz, d;
} T[N * 30];

#define son(p, s) T[p].son[s]

inline void ins(int v) {
	int p = 1;
	for (int i = 29; ~i; i--) {
		int g = v >> i & 1;
		if (son(p, g)) p = son(p, g);
		else p = son(p, g) = ++tot, T[p].d = i, id[i].pb(p);
		T[p].siz++;
	}
	if (T[p].siz == 1) s[p] = bf[c++];
}

int main() {
	n = read(), m = read() * 2ll; T[1].d = 30;
	for (int i = 1; i <= n; i++) ins(read());
	
	for (int i = tot; i; i--) {
		rep if (son(i, t)) s[son(i, t)][t][T[son(i, t)].d] += T[son(i, t)].siz;

		if (son(i, 0) && son(i, 1)) {
			s[i] = bf[c++];
			for (int k = T[i].d - 1; ~k; k--)
				rep s[i][t][k] = s[son(i, 0)][t][k] + s[son(i, 1)][t][k];
		} else if (son(i, 0) | son(i, 1)) s[i] = s[son(i, 0) | son(i, 1)];
	}

	id[30].pb(1); cor[1] = 1;
	for (int b = 29; ~b; b--) {
		ll cnt = 0;
		for (int i : id[b + 1]) if (cor[i])
			rep cnt += T[son(i, t)].siz * T[son(cor[i], t ^ 1)].siz;

		if (cnt >= m) {\/\/这一位为1
			lim |= 1 << b;
			for (int i : id[b + 1])
				rep cor[son(i, t)] = son(cor[i], t ^ 1);
		} else {\/\/这一位为0
			m -= cnt;
			for (int i : id[b + 1])
				rep {
					cor[son(i, t)] = son(cor[i], t);
					int x = son(cor[i], t ^ 1), y = son(i, t);
					if (x && y) {
						Add(ans, lim * T[x].siz * T[y].siz % Mod);
						for (int k = b; ~k; k--)
							rep Add(ans, (1ll << k) * s[x][t][k] * s[y][t ^ 1][k] % Mod);
					}
				}
		}
	}

	Add(ans, lim * m % Mod);

	printf("%lld", (ll) ans * (Mod + 1) \/ 2 % Mod);
	return 0;
}