问题 E: 异或和

问题 E: 异或和

时间限制: 1 Sec  内存限制: 128 MB
提交 状态

题目描述

有一个 n 个元素的数组 a ，设f(i,j)=ai xor aj。

现在你要求对于所有的 1≤i≤j≤n 的 f(i,j)之和。

输入

第一行，一个正整数 n 。
接下来 n 个数，表示 ai。

输出

仅一行，一个正整数，表示总和。

样例输入 Copy

3
1 2 3

样例输出 Copy

6

提示

对于 30% 的数据，n≤3000。
另外 20% 的数据，ai≤1。
对于 100% 的数据，1≤n≤2×10⁵,0≤ai≤10⁵。

#include<iostream>
#include<algorithm>
#include<map>
#include<string> 
#include <math.h> 
#include<memory.h>
#include<cstring>
#include<bits/stdc++.h> 
using namespace std;
typedef long long ll; 
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
const int INF=0x3f3f3f3f;
const int maxn=1e4+100;
const int maxa=1e9+10;
ll a[maxn];
ll n,x;
void inint(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>x;
        for(int j=0;j<20;j++){
            if(x&1<<j){
                a[j]++;
            }
        }
    }
}
int main(){
    inint();
    ll ans=0;
    for(int i=0;i<20;i++){
        ans+=(n-a[i])*a[i]*(1<<i);
    }
    printf("%lld",ans);
         
}