問題一覧 > 通常問題

No.1240 Or Sum of Xor Pair

レベル : / AI推定難易度 : 2000 / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 53
作問者 : chineristAC / テスター : tatyam
お気に入りにしたユーザー ProblemId : 5046 / 自分の提出
問題文最終更新日: 2020-09-23 18:16:43
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 267 (順位表) の他の問題:

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もしくは右上の雲マークをクリックしてアカウントを作成してください。