[原创]HDU 5269 ZYB loves Xor I [01字典树]【思维】

# include <bits/stdc++.h>
using namespace std;

# define INF        (~(1<<31))
# define INFLL      (~(1ll<<63))
# define pb         push_back
# define mp         make_pair
# define abs(a)     ((a)>0?(a):-(a))
# define lalal      puts("*******");
# define s1(x)      scanf("%d",&x)
# define Rep(a,b,c) for(int a=(b);a<=(c);a++)
# define Per(a,b,c) for(int a=(b);a>=(c);a--)
# define no         puts("NO")

typedef long long int LL ;
typedef unsigned long long int uLL ;

const int    MOD = 998244353;
const int    N   = 1500000+5;
const double eps = 1e-6;
const double PI  = acos(-1.0);
/***********************************************************************/

int trie[N][2],val[N],cnt;

void trieinsert(int x){
    int now = 0;
    for(int i=0;i<30;x>>=1,++i){
        if(!trie[now][x%2]) trie[now][x%2]=++cnt;
        now = trie[now][x%2];
        val[now]++;
    }
}

LL query(int x){
    int now = 0;
    LL ans =0ll;
    for(int i=0;i<30;x>>=1,++i){
        if(!trie[now][x%2]) trie[now][x%2]=++cnt;
        ans += (2ll<<i)*val[trie[now][1-x%2]];
        ans%=MOD;
        now = trie[now][x%2];
        val[now]++;
    }
    return ans ;
}

int main(){
    int _ = 1,kcase ;
    while(~scanf("%d",&_)){
        kcase = 0;
        while(_--){

            int n;
            scanf("%d",&n);

            cnt = 0;

            LL x;
            LL ans = 0ll;
            for(int i=0;i<n;i++){
                scanf("%I64d",&x);
                ans+=query(x);
                ans%=MOD;
                //printf("%I64d\n",ans);
                //trieinsert(x);
            }
            for(int i=0;i<=cnt;i++){
                trie[i][0]=trie[i][1]=val[i]=0;
            }
            printf("Case #%d: %I64d\n",++kcase,ans);
        }
    }
    return 0;
}