No.1240 Or Sum of Xor Pair
タグ : / 解いたユーザー数 53
作問者 :
tatyam
Problem Statement
You are given $N$ non-negative integers $A_i\ (1 \leq i \leq N)$ and a non-negative integer $X$.
Find the sum of $A_i\ or \ A_j$ over all pairs of integers $(i,j)$ satisfying the following conditions. If no pair of integers satisfies the conditions, output $0$.
Here, $xor$ denotes bitwise exclusive OR, and $or$ denotes bitwise OR.
Conditions
- $1 \le i < j \le N$
- $A_i\ xor\ A_j < X$
Input
$N\ \ X$ $A_1 \ \ A_2 \ \ \dots \ \ A_N$
- $2 \le N \le 2 \times 10^5 $
- $1 \le X \le 2^{18} $
- $0 \le A_i < 2^{18}\ (1 \le i \le N)$
- All input values are integers.
Output
Output the answer.
Print a newline at the end.
Sample
Sample 1
Input
4 4 1 2 3 4
Output
9
In this sample input, the pairs of integers satisfying the conditions are exactly $(1,2),(1,3),(2,3)$. The value of $A_i\ or\ A_j$ for each of them is $3$, so output their sum, $9$.
Sample 2
Input
4 2 11 13 15 32
Output
0
No pair of integers satisfies the conditions, so output $0$.
Sample 3
Input
20 234 133 338 412 435 199 431 247 371 183 491 365 492 474 164 204 163 262 304 391 289
Output
35708
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。