今天教练说让刷题，我去刷了。
刷到这道题，挺好的。
\(n\) 个同学打了 \(2^{m}\) 次比赛，
同学 \(j\) 第 \(i\) 次比赛的成绩是 \(a_j \operatorname{xor} i\)，
每次获得的积分是排名 \(x\) 的平方。
输出每个同学积分和模 \(1e9+7\) 后的的异或和。
我们考虑：
-
一个人的积分由排名比起靠前的人的点对提供；
-
很显然一个人一定会败给某个人 \(2^{m-1}\) 次，再胜某个人 \(2^{m-1}\) 次 。
那就可以搞 \(\texttt{Trie树}\) 了！
首先把所有的值插进去。
然后开始 \(\texttt{dfs}\) ，一边记录点对数和之前与之在不同子树的数的个数。
#include <iostream>
#define llt long long int
const int moyn = 1e9+7;
const int N = 1e7+10;
int n, m;
int trie[N][2];
int trie_tot;
llt size[N];
llt ans;
#define lid(u) trie[u][0]
#define rid(u) trie[u][1]
void insert(int x) {
int u = 0, sid;
for(register int i = m-1;i >= 0;--i) {
sid = (x>>i)&1;
if(!trie[u][sid])
trie[u][sid] = ++trie_tot;
u = trie[u][sid];
++size[u];
}
}
void dfs(int u,llt sum,llt num) {
if(lid(u))
dfs(lid(u),(sum+size[rid(u)]*size[rid(u)]%moyn*(1LL<<(m-1))%moyn+size[rid(u)]*num%moyn*(1LL<<(m-1))%moyn)%moyn,num+size[rid(u)]);
if(rid(u))
dfs(rid(u),(sum+size[lid(u)]*size[lid(u)]%moyn*(1LL<<(m-1))%moyn+size[lid(u)]*num%moyn*(1LL<<(m-1))%moyn)%moyn,num+size[lid(u)]);
if(!lid(u)&&!rid(u))
ans ^= sum;
}
int a;
int main() {
scanf("%d %d",&n,&m);
for(register int i = 1;i <= n;++i) {
scanf("%d",&a);
insert(a);
}
dfs(0,0LL,0LL);
printf("%lld\n",ans);
return 0;
}