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