【求和】

题目描述

你的任务十分简单:
给定长度为 n 的序列 A[i],求所有 A[i] xor A[j] (i<j) 的值之和。

输入格式

第一行一个整数 N 。
接下来 N 行,第 i 行为 A[i] 。

输出格式

输出题目要求的值。

样例数据 1

输入

3
7
3
5

输出

12

备注

【数据范围】
对于 40% 的数据,N<=5000;
对于 100% 的数据,N<=100000;a[i]<=10000。

大水题,只需要把数都转成二进制然后看到第i个数的第j位为止有多少个0和多少个1就行了,然后如果第j位为0就看后面有多少个1跟它异或,反之亦然,0/1对答案的贡献是k*(1<<j-1)(k就是异或不为0的次数)。

下面是代码:

 

stdKonjac

stdKonjac

一只挣扎的蒟蒻ACMer

评论太激烈有些评论需要亲动动手指翻页

留下你的评论

*评论支持代码高亮<pre class="prettyprint linenums">代码</pre>

*