bestcoders

ZYB loves Xor I

Accepts: 142 Submissions: 696 Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others) 問題描述

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

 

#include 
#include 
#include 
#include 

using namespace std;

const long long MOD = 998244353;
const int maxn = 30;
const int M = 2;
long long  ans;

struct Node
{
    int v;
    Node *next[M];
};

struct Tree
{
    Node *root;
    int v;

    Tree()//constructor
    {
        root = new Node;
        root->v = 0;
        for(int i=0; inext[i] = NULL;
    }

    void insert(int t)
    {
        Node *p = root, *q;

        for(int i=0; inext[tmp] == NULL)
            {
                q = new Node;
                q->v = 1;
                for(int i=0; inext[i] = NULL;
                p->next[tmp] = q;
                p = q;
            }
            else
            {
                p = p->next[tmp];
                p->v++;
            }
        }
    }

    void find(int t)
    {
        Node *p = root;
        for(int i=0; inext[tmp^1] != NULL)
                ans = (ans + (p->next[tmp^1]->v)*(long long)(1<next[tmp];
        }
    }
};

const int N = 50005;
int a[N];
int kase = 0;

int main()
{
    int T, n;
    scanf(%d, &T);
    while(T--)
    {
        ans = 0;
        Tree tree;
        scanf(%d, &n);
        for(int i=0; i