ZYB loves Xor I

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 979 Accepted Submission(s): 436

Problem Description

Memphis loves xor very musch.Now he gets an array A.The length of A is n.Now he wants to know the sum of all (lowbit(

Ai xor

Aj))

(i,j∈[1,n])

We define that lowbit(x)=

2k,k is the smallest integer satisfied ((

x and

2k)>0)

Specially,lowbit(0)=0

Because the ans may be too big.You just need to output

ans mod 998244353

Input

Multiple test cases, the first line contains an integer T(no more than 10), indicating the number of cases. Each test case contains two lines

The first line has an integer

The second line has

n integers

A1,

A2....

n∈[1,5∗104]，

Ai∈[0,229]

Output

For each case, the output should occupies exactly one line. The output format is Case #x: ans, here x is the data number begins at 1.

Sample Input

      2 5 4 0 2 7 0 5 2 6 5 4 0 

Sample Output

      Case #1: 36 Case #2: 40 

题意：求∑ lowbit(a xor b) a,b属于这n个数。(a, b)和(b, a)算两次。

题解：观察发现对于任意一个数 x 来说，只要前 i-1 位和其它数相等，第i位不相等。那么 ans += cnt * pow(2, i-1);

cnt 为和它前i-1个前缀都相等的数的个数。可以利用字典树边插入边更新ans，最后ans*2就是答案。

ps: SB 错误错了一天。。。#define N 50000+5 那个开数组的时候 N*33就变成了 50000+5*33。就错了一天！！！！！

代码：

1 #include 
       
         2 #include 
        
          3 #include 
         
           4 #include 
          
            5 #include 
           
             6 #include 
            
              7 #include 
             
               8 #include 
              
                9 #include 
               
                10 #include 
                
                 11 #include 
                 
                  12 #include 
                  13 #define rep(i,a,b) for(int i = a;i <= b;++ i)14 #define per(i,a,b) for(int i = a;i >= b;-- i)15 #define mem(a,b) memset((a),(b),sizeof((a)))16 #define FIN freopen("in.txt","r",stdin)17 #define FOUT freopen("out.txt","w",stdout)18 #define IO ios_base::sync_with_stdio(0),cin.tie(0)19 #define mid ((l+r)>>1)20 #define ls (id<<1)21 #define rs ((id<<1)|1)22 #define N 5000523 #define INF 0x3f3f3f3f24 #define INFF 0x3f3f3f3f3f3f3f25 #define mod 99824435326 typedef long long ll;27 using namespace std;28 29 int T,n;30 ll x,ans,qpow[60];31 struct Trie{32 int ch[N*33][2], val[N*33], tol;33 void Init() { mem(ch[0], -1); mem(val, 0); tol = 1; }34 35 void insert(ll x){36 int u = 0;37 rep(i, 0, 29){38 int v = (x&1);39 if(ch[u][v^1] != -1){40 ans += qpow[i] * val[ch[u][v^1]];41 if(ans > mod) ans %= mod;42 }43 if(ch[u][v] == -1){44 mem(ch[tol], -1);45 ch[u][v] = tol++;46 }47 x >>= 1;48 u = ch[u][v];49 val[u]++;50 }51 }52 }trie;53 void fuc(){54 qpow[0] = 1;55 rep(i, 1, 30) qpow[i] = (qpow[i-1]%mod * 2)%mod; 56 }57 int main()58 {IO;59 fuc();60 //FIN;61 cin >> T;62 int w_w = 0;63 while(T--){64 cin >> n;65 66 ans = 0;67 trie.Init();68 rep(i, 1, n){69 cin >> x;70 trie.insert(x);71 }72 cout << "Case #" << ++w_w << ": " << ans*2%mod << endl;73 }74 return 0;75 }