题意：

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个整数为Ai

n∈[1,5∗104]，Ai∈[0,229]

每组数据输出一行Case #x: ans。x表示组数编号。从1開始。ans为所求值。

2

5

4 0 2 7 0

5

2 6 5 4 0

Case #1: 36

Case #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<iostream>

#include<cstring>

#include<cstdio>

#include<algorithm>

using namespace std;

typedef long long LL;

#define MAXN 5000500

#define lowbit(i) ((i) & (-(i)))

#define MOD 998244353

struct 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);

    }

}