分数: 400 点
问题陈述
我们有 N 整数。的 i- 第一个整数是 A_i.
查找 \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j),模数 (10^9+7).
什么是 \text{ XOR }?
整数的异或 A 和 B, A \text{ XOR } B,定义如下:
- 当 A \text{ XOR } B 以二为基数写入,即 2^k的地点 (k \geq 0)是 1 如果 A or B,但不是两者都有 1 在 2^k的地点,以及 0 否则。
约束
- 2 \leq N \leq 3 \times 10^5
- 0 \leq A_i < 2^{60}
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N A_1 A_2 ... A_N
输出
打印该值 \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j),模数 (10^9+7).
示例输入 1
3 1 2 3
示例输出 1
6
我们有 (1\text{ XOR } 2)+(1\text{ XOR } 3)+(2\text{ XOR } 3)=3+2+1=6.
示例输入 2
10 3 1 4 1 5 9 2 6 5 3
示例输出 2
237
示例输入 3
10 3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820
示例输出 3
103715602
打印模数之和 (10^9+7).