/ 
Time Limit: 2 sec / Memory Limit: 1024 MB
配点 : 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) の位の数は、A, B を二進表記した際の 2^k の位の数のうち一方のみが 1 であれば 1、そうでなければ 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 で割った余りを出力してください。
Score : 400 points
Problem Statement
We have N integers. The i-th integer is A_i.
Find \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j), modulo (10^9+7).
What is \text{ XOR }?
The XOR of integers A and B, A \text{ XOR } B, is defined as follows:
- When A \text{ XOR } B is written in base two, the digit in the 2^k's place (k \geq 0) is 1 if either A or B, but not both, has 1 in the 2^k's place, and 0 otherwise.
Constraints
- 2 \leq N \leq 3 \times 10^5
- 0 \leq A_i < 2^{60}
- All values in input are integers.
Input
Input is given from Standard Input in the following format:
N A_1 A_2 ... A_N
Output
Print the value \sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j), modulo (10^9+7).
Sample Input 1
3 1 2 3
Sample Output 1
6
We have (1\text{ XOR } 2)+(1\text{ XOR } 3)+(2\text{ XOR } 3)=3+2+1=6.
Sample Input 2
10 3 1 4 1 5 9 2 6 5 3
Sample Output 2
237
Sample Input 3
10 3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820
Sample Output 3
103715602
Print the sum modulo (10^9+7).