Spoj-BITDIFF Bit Difference

Given an integer array of N integers, find the sum of bit differences in all the pairs that can be formed from array elements. Bit difference of a pair (x, y) is the count of different bits at the same positions in binary representations of x and y. For example, bit difference for 2 and 7 is 2. Binary representation of 2 is 010 and 7 is 111 (first and last bits differ in two numbers).

Input

Input begins with a line containing an integer T(1<=T<=100), denoting the number of test cases. Then T test cases follow. Each test case begins with a line containing an integer N(1<=N<=10000), denoting the number of integers in the array, followed by a line containing N space separated 32-bit integers.

Output

For each test case, output a single line in the format Case X: Y, where X denotes the test case number and Y denotes the sum of bit differences in all the pairs that can be formed from array elements modulo 10000007.

Example

Input:

1

4

3 2 1 4

Output:

Case 1: 22

求和：对任意一对数(a,b)二进制展开，这两个数有多少位是01不同的

把每一位拆开来，假设第i位是1的有bit[i]个，答案就是Σ2*bit[i]*(n-bit[i])

 #include<cstdio>

 #include<iostream>

 #include<cstring>

 #include<cstdlib>

 #include<algorithm>

 #include<cmath>

 #include<queue>

 #include<deque>

 #include<set>

 #include<map>

 #include<ctime>

 #define LL long long

 #define inf 0x7ffffff

 #define pa pair<int,int>

 #define mkp(a,b) make_pair(a,b)

 #define pi 3.1415926535897932384626433832795028841971

 #define mod 10000007

 using namespace std;

 inline LL read()

 {

     LL x=,f=;char ch=getchar();

     while(ch<''||ch>''){if(ch=='-')f=-;ch=getchar();}

     while(ch>=''&&ch<=''){x=x*+ch-'';ch=getchar();}

     return x*f;

 }

 int n;

 LL ans;

 int a[];

 int bit[];

 inline void work(int cur)

 {

     n=read();

     for (int i=;i<=n;i++)a[i]=read();

     ans=;

     memset(bit,,sizeof(bit));

     for (int i=;i<=n;i++)

         for (int j=;j<=;j++)

         if (a[i] & (<<j))bit[j]++;

     for (int j=;j<=;j++)

         ans+=(LL)bit[j]*(n-bit[j])*;

     printf("Case %d: %lld\n",cur,ans%mod);

 }

 int main()

 {

     int T=read(),tt=;

     while (T--)work(++tt);

 }

Spoj BITDIFF

巴特西

Spoj-BITDIFF Bit Difference

Input

Output

Example

最新文章

热门文章