【NOIP模拟赛】求和式

2014年4月5日1,1120

题目描述

作为本场考试的第一题,你的任务十分简单:

给定长度为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

题解

转为二进制

一位一位处理

统计第i位所有数字0或1的个数,记为a[i]和b[i]

则对于答案的贡献为a[i]*b[i]*1<<(i-1)