求和式(x3)
題目描述
作為本場考試的第一題，你的任務十分簡單：
給定長度為n的序列A[i]，求所有A[i]xor A[j] (i<j)的值之和
輸入
第一行一個整數N
接下來N行，第i行為A[i]
輸出
所需的值
樣例輸入
3
7
3
5
樣例輸出
12
樣例解釋
7 xor 3+3 xor 5+7 xor 5 = 4+6+2 = 12
數據范圍
對於40%的數據，N<=5000
對於100%的數據，N<=1000000
c++中的%lld千萬別用啊 ，各種坑人！
統一用cout
另外C++中(long long)（1<<k)
這裡要轉，不然必wa
千萬要先乘，和別的數乘完不定什麼數了……
本題是位運算分解成一位一位運算（重要性質）
[cpp]
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<iostream>
#include<functional>
#include<algorithm>
using namespace std;
#define MAXN (100+10)
int n,a,c[MAXN][2]={0};// 1<<i =(0.1)
int main()
{
freopen("x3.in","r",stdin);
freopen("x3.out","w",stdout);
/* for (int i=0;i<=100;i++)
{
cout<<c[i][0]<<' '<<c[i][1]<<endl;
}
*/ long long ans=0;
scanf("%d",&n);
int len=0;
for (int i=1;i<=n;i++)
{
scanf("%d",&a);
int tot=-1;
int j=100;
while (j--) {c[++tot][a%2]++;a/=2;}
len=len<tot?tot:len;
}
/* for (int i=0;i<=100;i++)
{
cout<<c[i][0]<<' '<<c[i][1]<<endl;
}
*/
for (int i=0;i<=28;i++)
{
ans+=(long long)(1<<i)*(long long)c[i][1]*(long long)(n-c[i][1]);
// cout<<ans<<endl;
}
/*
for (int i=0;i<=len;i++) cout<<c[i][0]<<' '<<c[i][1]<<' '<<endl;
*/
// printf("%lld\n",ans);
cout<<ans<<endl;
// while (1);
return 0;
}
