Skip to content

1439: 小V的lowbit

题目

题目描述

这天,小V在学习lowbit。

lowbit(x)的意思是将 x 分解成二进制,它的值就是$2^k$,

其中 k 是最小的满足(x & $2^k$)>0 的数。(&是二进制中的 and 运算)

小V甚至知道 lowbit(x)=(x&-x)。但这并没什么用处。

现在 小V 有了 n 个数字,为了使自己更好的理解 lowbit 是什么意思。

它想对所有 $n^2$ 个二元组求 lowbit。

具体的,对于一个二元组(ai,aj),它的值为 lowbit(ai xor aj) (xor 表示异或的意思,在程序中我们可用ai^aj来计算ai xor aj)

例如 5的二进制表示为101,2的二进制表示为10,我们可以得到 5 xor 2 = $(111)_2$ = 7

(对数的每一个二进制位进行比较,若不同,则该位为1,若相同,则该位为0,即1 xor 0 =1, 0 xor 1 =1 , 0 xor 0 =0, 1 xor 1 =0)

那么总共有 $n^2$ 对二元组,小V想知道所有二元组的值加起来是多少。

这个答案可能很大,你只需输出这个值对 1000000007 取模后的结果就可以了。

输入格式

第一行一个数 n,表示有 n 个这样的数字。

第二行 n 个数 ai

输出格式

一个数表示答案。

样例输入

5

1 2 3 4 5

样例输出

32

数据范围

对于 30%的数据 n<=1000。

对于另外 10%的数据 ai<=1。

对于再另外 10%的数据 ai<=3。

对于再再另外 20%的数据 ai<1024。

对于 100%的数据 1<=n<=100000,0<=ai<2^30。

Oops! 本题目还没有解答!

助教老师们编题的速度,已经超过了解题的速度!

OJ翻了一新,但本解答集还大多用的是2017-2019级,甚至更早的同学们贡献的答案。

如果你已经AC了,可以的话,请您参考添加页面,与大家一起分享你的题解!