#ABC147D. Xor Sum 4
Xor Sum 4
题目描述
We have integers. The -th integer is .
Find $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j)$, mod .
What is ?
The XOR of integers and , , is defined as follows:
- When is written in base two, the digit in the 's place () is if either or , but not both, has in the 's place, and otherwise.
For example, . (In base two: .)
我们有 个整数。其中 个整数是 。
求 $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j)$ , mod .
是多少??
整数 和 的 XOR 即 的定义如下:
- 当以二进制写入 时,如果 或 (而不是两者)的 的 位上有 ,那么 的 位上的数字就是 ,否则就是 。
例如, 。(二进制: )。
输入格式
输入内容按以下格式标准输入:
输出格式
打印数值 $\sum_{i=1}^{N-1}\sum_{j=i+1}^{N} (A_i \text{ XOR } A_j)$ , mod .
样例 #1
样例输入 #1
3
1 2 3
样例输出 #1
6
样例 #2
样例输入 #2
10
3 1 4 1 5 9 2 6 5 3
样例输出 #2
237
样例 #3
样例输入 #3
10
3 14 159 2653 58979 323846 2643383 27950288 419716939 9375105820
样例输出 #3
103715602
说明
数据规模与约定
- 所有输入值均为整数。
样例 解释
我们有 $(1\text{ XOR } 2)+(1\text{ XOR } 3)+(2\text{ XOR } 3)=3+2+1=6$ 。
样例 解释
打印和的模数 。