問題一覧 > 通常問題

No.1240 Or Sum of Xor Pair

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 41
作問者 : chineristACchineristAC / テスター : tatyamtatyam
9 ProblemId : 5046 / 出題時の順位表
問題文最終更新日: 2020-09-23 18:16:43

問題文

$N$ 個の非負整数 $A_i\ (1 \leq i \leq N)$ と非負整数 $X$ が与えられます。

以下の条件をみたすすべての整数の組 $(i,j)$ に対する $A_i\ or \ A_j$ の総和を求めてください。条件を満たす整数の組が存在しない場合は $0$ を出力してください。

ここで $xor$ はビットごとの排他的論理和、 $or$ はビットごとの論理和を表します。

条件

  • $1 \le i < j \le N$
  • $A_i\ xor\ A_j < X$

入力

$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)$
  • 与えられる入力はすべて整数

出力

答えを出力してください。
最後に改行してください。

サンプル

サンプル1
入力
4 4
1 2 3 4
出力
9

この入力例で条件を満たす整数の組は $(1,2),(1,3),(2,3)$ ですべてです。これらに対する $A_i\ or\ A_j$ の値はすべて $3$ なのでそれらの和である $9$ を出力します。

サンプル2
入力
4 2
11 13 15 32 
出力
0

条件を満たす整数の組は存在しないので $0$ を出力します。

サンプル3
入力
20 234
133 338 412 435 199 431 247 371 183 491 365 492 474 164 204 163 262 304 391 289
出力
35708

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。