uestc 1709 Binary Operations 位运算的灵活运用

Binary Operations

Time Limit: 2000 ms Memory Limit: 65535 kB Solved: 56 Tried: 674

Description

Bob has a sequence of N integers. They are so attractive, that Alice begs to have a continued part of it(a continued part here also means a continued subsequence). However, Bob only allows Alice to chose it randomly. Can you give the expectation of the result of the bitwise AND, OR, XOR of all the chosen numbers?

Input

First line of the input is a single integer T(1 <= T <= 50), indicating there are T test cases.

The first line of each test case contains a single number N(1 <= N <= 50000).

The second line contains N integers, indicating the sequence.

All the N integers are fit in [0, 10^9].

Output

For each test case, print "Case #t: a b c" , in which t is the number of the test case starting from 1, a is the expectation of the bitwise AND, b is the expectation of OR and c is the expectation of XOR.

Round the answer to the sixth digit after the decimal point.

Sample Input

3
2
1 2
3
1 2 3
3
2 3 4

Sample Output

Case #1: 1.000000 2.000000 2.000000
Case #2: 1.333333 2.500000 1.666667
Case #3: 1.833333 4.333333 3.666667

Hint

AND is a binary operation, performed on two numbers in binary notation. First, the shorter number is prepended with leading zeroes until both numbers have the same number of digits (in binary). Then, the result is calculated as follows: for each bit where the numbers are both 1 the result has 1 in its binary representation. It has 0 in all other positions.

OR is a binary operation, performed on two numbers in binary notation. First, the shorter number is prepended with leading zeroes until both numbers have the same number of digits (in binary). Then, the result is calculated as follows: for each bit where the numbers are both 0 the result has 0 in its binary representation. It has 1 in all other positions.

XOR is a binary operation, performed on two numbers in binary notation. First, the shorter number is prepended with leading zeroes until both numbers have the same number of digits (in binary). Then, the result is calculated as follows: for each bit where the numbers differ the result has 1 in its binary representation. It has 0 in all other positions.

Source

Sichuan State Programming Contest 2012

  1 /*
  2 
  3 
  4 求期望，如果暴力，超时。上次比赛没有人做出来，看了解题思路，省赛完了再来写的
  5 
  6 用位运算，每次处理32次。
  7 如果暴力，虽然前面比较少，但是，随着n的增大，次数将增加很大。
  8 
  9 在//！！！处，原来不知道怎么处理，后来推导过程得出的。
 10 
 11 */
 12 
 13 
 14 #include<iostream>
 15 #include<cstdio>
 16 #include<cstdlib>
 17 #include<cstring>
 18 using namespace std;
 19 typedef long long  LL;
 20 
 21 LL a[50002];//看开始用int，错误了。
 22 LL f[33];
 23 LL tmp[33];
 24 LL vis[33];
 25 
 26 void make_init(LL x)
 27 {
 28     LL i;
 29     memset(f,0,sizeof(f));
 30     i=32;
 31     while(x)
 32     {
 33         f[i]=x&1;
 34         x=x>>1;
 35         i--;
 36     }
 37 }
 38 
 39 void solve(LL t,LL n)
 40 {
 41     LL i,j;
 42     LL Sum=n*(n+1)/2;
 43     LL XOR=0,AND=0,OR=0;
 44     printf("Case #%lld: ",t);
 45 
 46     memset(tmp,0,sizeof(tmp));
 47     memset(vis,0,sizeof(vis));
 48     for(i=1; i<=n; i++)
 49     {
 50         make_init(a[i]);
 51 
 52         if(i==1)
 53         {
 54             for(j=1; j<=32; j++)
 55             {
 56                 tmp[j]=f[j];
 57                 vis[j]=f[j];
 58             }
 59         }
 60         else
 61         {
 62             for(j=1; j<=32; j++)
 63             {
 64                 if(f[j]==0)tmp[j]=0;
 65                 tmp[j]+=f[j];
 66             }
 67             for(j=1; j<=32; j++)
 68                 vis[j]=vis[j]+tmp[j];
 69         }
 70     }
 71     for(i=1; i<=32; i++)
 72         AND=AND*2+vis[i];
 73     printf("%.6lf",(double)(AND*1.0/Sum));
 74 
 75 
 76     memset(tmp,0,sizeof(tmp));
 77     memset(vis,0,sizeof(vis));
 78     for(i=1; i<=n; i++)
 79     {
 80         make_init(a[i]);
 81         if(i==1)
 82         {
 83             for(j=1; j<=32; j++)
 84             {
 85                 tmp[j]=f[j];
 86                 vis[j]=f[j];
 87             }
 88         }
 89         else
 90         {
 91             for(j=1; j<=32; j++)
 92             {
 93                 if(f[j]==1) tmp[j]=i-1;//!!!!!
 94                 tmp[j]=tmp[j]+f[j];
 95             }
 96             for(j=1; j<=32; j++)
 97                 vis[j]=vis[j]+tmp[j];
 98         }
 99     }
100     for(j=1; j<=32; j++)
101         OR=OR*2+vis[j];
102     printf(" %.6lf",(double)(OR*1.0/Sum));
103 
104     memset(tmp,0,sizeof(tmp));
105     memset(vis,0,sizeof(vis));
106     for(i=1; i<=n; i++)
107     {
108         make_init(a[i]);
109         if(i==1)
110         {
111             for(j=1; j<=32; j++)
112             {
113                 tmp[j]=f[j];
114                 vis[j]=f[j];
115             }
116         }
117         else
118         {
119             for(j=1; j<=32; j++)
120             {
121                 if(f[j]==1) tmp[j]=i-1-tmp[j];//!!!!!
122                 tmp[j]=tmp[j]+f[j];
123             }
124             for(j=1; j<=32; j++)
125                 vis[j]=vis[j]+tmp[j];
126         }
127     }
128     for(j=1; j<=32; j++)
129         XOR=XOR*2+vis[j];
130     printf(" %.6lf
",(double)(XOR*1.0/Sum));
131 
132 }
133 
134 int main()
135 {
136     LL T,n,i,j;
137     scanf("%lld",&T);
138     for(j=1; j<=T; j++)
139     {
140         scanf("%lld",&n);
141         for(i=1; i<=n; i++)
142         {
143             scanf("%lld",&a[i]);
144         }
145         solve(j,n);
146     }
147     return 0;
148 }