uestc1041Hug the princess

There is a sequence with  n n elements. Assuming they are  a1,a2,?,an a1,a2,?,an.

Please calculate the following expession.

∑1≤i<j≤n(ai∧aj)+(ai|aj)+(ai&aj) ∑1≤i<j≤n(ai∧aj)+(ai|aj)+(ai&aj)

In the expression above, ^ | & is bit operation. If you don’t know bit operation, you can visit

http://en.wikipedia.org/wiki/Bitwise_operation

to get some useful information.

Input

The first line contains a single integer  n n, which is the size of the sequence.

The second line contains  n n integers, the  ith ith integer  ai ai is the  ith ith element of the sequence.

1≤n≤100000,0≤ai≤100000000 1≤n≤100000,0≤ai≤100000000

Output

Print the answer in one line.

Sample input and output

2
1 2

6

Hint

Because the answer is so large, please use long long instead of int. Correspondingly, please use %lld instead of %d to scanf and printf.

Large input. You may get Time Limit Exceeded if you use "cin" to get the input. So "scanf" is suggested.

Likewise, you are supposed to use "printf" instead of "cout".

求出二进制位数计算出每个数的对结果的贡献即可

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<algorithm>
#include<queue>
#include<list>
#include<cmath>
#include<vector>
using namespace std;
const int maxn=100010;
long long bit[30][2];
long long num2[maxn][30];
long long num[maxn];
long long bitnum[maxn];
long long POW[30];
int main()
{POW[0]=1;for(int i=1;i<30;++i){POW[i]=POW[i-1]*2ll;}int n,i,j,k;while(scanf("%d",&n)!=EOF){memset(bit,0,sizeof(bit));memset(num2,0,sizeof(num2));for(i=1;i<=n;++i){scanf("%lld",&num[i]);long long temp=num[i],cnt=0;while(temp){bit[cnt][temp&1]++;num2[i][cnt]=temp&1;temp>>=1;cnt++;}for(j=cnt;j<30;++j)bit[j][0]++;}long long ans1=0;long long ans=0;	for(i=1;i<=n;++i){for(j=0;j<30;++j){if(num2[i][j]==1){ans=ans+(bit[j][0]*POW[j]);ans=ans+((n-i)*POW[j]);ans=ans+((bit[j][1]-1)*POW[j]);bit[j][1]--;}else {ans=ans+(bit[j][1]*POW[j]);ans=ans+(bit[j][1]*POW[j]);bit[j][0]--;}}}printf("%lld\n",ans);}return 0;
}