http://192.168.121.103:8088/p/2729

#黄，#折半

枚举

一共就四个数，直接枚举。
时间复杂度 $\operatorname{O}(n^4)$。 期望得分 20 pts。

还是枚举？

注意到，我们期望的时间复杂度就是 $\operatorname{O}(n^2)$，与 $\operatorname{O}(n^4)$ 只有一步之遥。

注意到，这是指数的折半，samm 带领我们想到了折半！

题目中有变量大小限制，不可以一次性枚举 $(b_1, b_2)$，生成一个桶，然后再枚举 $(b_3, b_4)$。

因此，我们需要将枚举 $(b_1, b_2)$ 与 $(b_3, b_4)$ 合为一体。

算法流程

• 我们枚举右区间的左端点 $b_3$，也可以说是分界线。
  • 枚举 $b_4$，并且用桶更新答案，$ans \gets ans + cnt_{a_{b_3} \oplus a_{b_4}}$。
  • 将 $b_3$ 变成 $b_2$，向右扩展左区间。枚举 $b_1$，对桶修改，$cnt_{a_{b_1} \oplus a_{b_2}} \gets cnt_{a_{b_1} \oplus a_{b_2}} + 1$。

:::success[Code]

#include<bits/stdc++.h>
using namespace std;
const int N = 5e3 + 10, M = (1 << 24) + 10;
int n, a[N];
long long ans;
int cnt[M];
int main(){
	cin >> n;
	for(int i = 1; i <= n; i ++) cin >> a[i];
	for(int i = 1; i <= n; i ++){
		for(int j = i + 1; j <= n; j ++){
			ans += cnt[a[i] ^ a[j]];
		}
		for(int j = 1; j < i; j ++){
			cnt[a[i] ^ a[j]] ++;
		}
	}
	cout << ans;
	return 0;
}

:::