做之前：有点囊啊…………
做之后：🍭超甜题$n^2$扫一遍就过了，折半在哪？

正题

先看题目，$n\le5000$，先考虑$O(n^4)$的大暴力骗分. $Code:$

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,a[5005],ans;
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	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++){
			for(int p=j+1;p<=n;p++){
				for(int k=p+1;k<=n;k++){
					if((a[i]^a[j]^a[p]^a[k])==0){
						ans++;
					}
				}
			}
		}
	}
	cout<<ans;
	return 0;
}

but……，just 20pts……
所以考虑优化……

优化

很明显$5000\times5000=25000000<5\times10^8$故$O(n^2)$可过，那我们怎么搞$O(n^2)$呢？

注意到，$a_i\le10^6$,我们把$10^6$扔进计算器得到$11110100001001000000_2$，那位运算的答案就很有限了
故再用计算器算一下可知$a_{b_1}\oplus a_{b_2}\oplus a_{b_3}\oplus a_{b_4}\le 11111111111111111111_2=1048575$.

也就是说我们可以用一个桶排计数，把某个下标之前的$x$个数的异或结果$(1\le x\le 3)$.
那$x$应该取多少呢？(都是折半了，当然取2了)

那么为什么取$2$呢？？？

我们容易想到，枚举$1$~$n$的所有二元组$(x,y)$满足$1\le x<y\le n$的$O(n^2)$做法，即以下两段$Code$:

for(int i=2;i<=n;i++){
    for(int j=1;j<i;j++){
        //其中(j,i)为满足条件的所有情况
    }
}

以及

for(int i=1;i<=n;i++){
    for(int j=i+1;j<=n;j++){
        //其中(i,j)为满足条件的所有情况
    }
}

那我们如何引入这道题呢，我们想：以$i,i-1$两个下标为界，分别枚举$1$~$i$和$i+1$~$n$两个区间内的所有满足上述条件的二元组，则可以保证找出的四个下标$b_1,b_2,b_3,b_4$绝对满足$b_1<b_2<b_3<b_4$，若其对应数组中值的异或值为0，就是一个满足的答案.
因此有以下结论：

1. 对于$1$~$i$范围内求出的二元组，对区间$i+1$至$n-1$到$n$的各个区间的结果都是可做出合法贡献的.
2. 对于两个数$a,b$若$a\oplus b=0$，则$a=b$

因此我们有了桶排计数的基础，每当枚举区间$1$~$i$,将$a_j\oplus a_i$的值累加入桶，然后再枚举区间$i+1$~$n$，其中$ans$的累加值为$a_{i+1}\oplus a_j$对应的桶中的累加值，那答案就很显而易见了.

对于其时间复杂度：为双层循环嵌套，易知复杂度为$O(n^2)$

$Code:$

//这么简单的Code不会还要注释吧
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=5e6+5;
int n,a[5005],ans;
int t[N];
signed main()
{
	ios::sync_with_stdio(0);
	cin.tie(0);cout.tie(0);
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>a[i];
	}
  //下标为什么从这开始自己想
	for(int i=2;i<=n-2;i++){
		for(int j=1;j<i;j++){
			t[a[i]^a[j]]++;
		}
		for(int j=i+2;j<=n;j++){
			ans+=t[a[i+1]^a[j]];
		}
	}
	cout<<ans;
	return 0;
}

最后不要忘了：十年OI一场空，_____________

🍭超甜题 $n^2$扫一遍就过了，折半在哪？