题意：
ZYB喜欢研究Xor，如今他得到了一个长度为n的数组A。
于是他想知道：对于全部数对(i,j)(i∈[1,n],j∈[1,n])。lowbit(AixorAj)之和为多少.因为答案可能过大，你须要输出答案对998244353取模后的值 定义lowbit(x)=2k，当中k是最小的满足(x and 2k)>0的数 特别地：lowbit(0)=0
输入描写叙述
一共T(T≤10)组数据，对于每组数据：第一行一个正整数n，表示数组长度第二行n个非负整数，第i个整数为Ain∈[1,5∗104]，Ai∈[0,229]
输出描写叙述
每组数据输出一行Case #x: ans。x表示组数编号。从1開始。ans为所求值。
输入例子
254 0 2 7 052 6 5 4 0
输出例子
Case #1: 36Case #2: 40官方题解：
我们考虑，当A xor B的答案为2p时，A和B表示成二进制数后末p−1位肯定同样
于是我们维护一颗字母树。将每一个数表示成二进制数后翻转能够下。插入字母树
统计答案时，我们找出Ai的二进制数翻转后在字母树上的路径，对于路径上每一个点x。设他走的边是v。且当前为
第k位，则和他xor后lowbit为2k的数的个数为trans(x,v^1)的子树大小。
trans(x,v)表示字母树上在结点x，走连出去的字母为v的边到达的结点
时间复杂度：O(nlogA)总结：
1.这道题一直拖着没有写总结，感觉一直没有从变化中观察到不变
2.当时自己比赛没有做出来这个题目，可能当时校赛得了第7。导致有些自负吧，事实上还是能力的不足，好的行为并没
有培养成好的习惯。
3.后来也是看了一眼bc群上的说trie，才想到的。以下总结一下失败的原因吧。
4.我開始是想对于除0以外的数按lowbit值排序（也就是最低位出现的1排序），lowbit同样的再依照除此位的lowbit排
序，没搞出来。
5.假设刚才的思路清晰之后，事实上就是分层处理，按lowbit值同样的为一组，对于不同组直接能够算出，对于同组，减
掉刚才的lowbit。再求lowbit。继续分组运算。
6.这不就是不停地分层处理吗？！
那能够用trie这样的数据结构直接来做
7.比赛时候没有把算法考虑清楚就急忙写代码，以后不许再犯同样的大忌了
#include#include #include #include using namespace std;typedef long long LL;#define MAXN 5000500#define lowbit(i) ((i) & (-(i)))#define MOD 998244353struct Trie{ int ch[MAXN][2],val[MAXN],cnt; LL ans; void init() { ans = cnt = val[0] = ch[0][0] = ch[0][1] = 0; } void insert(int v) { val[0]++; int deep = 0,num = val[0],next = 0; for(int i = 0;i < 30;i++) { int c = v & 1; if(!ch[next][c]) { ch[next][c] = ++cnt; val[cnt] = ch[cnt][0] = ch[cnt][1] = 0; } val[ch[next][c]]++; deep++; ans += ((num - val[ch[next][c]]) << deep); ans %= MOD; next = ch[next][c]; v >>= 1; num = val[next]; } }}trie;int main(){ int _,n,cur; for(int kcas = scanf("%d",&_);kcas <= _;kcas++) { trie.init(); for(int i = scanf("%d",&n);i <= n;i++) { scanf("%d",&cur); trie.insert(cur); } printf("Case #%d: %I64d\n",kcas,trie.ans); }}