求和式 (C++ 坑爹的<<,>>,%lld)

求和式(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

千万要先乘,和别的数乘完不定什么数了……

本题是位运算分解成一位一位运算(重要性质)

#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;
}