← 返回题目列表

AtCoder · abc147_d

D. 异或和 4

中文机器翻译题面 查看原题

分数: 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 否则。
例如, 3 \text{ XOR } 5 = 6。 (在基数二中: 011 \text{ XOR } 101 = 110.)

约束

  • 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).