No.911 ラッキーソート

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 66
作問者 : TaprisちゃんTaprisちゃん / テスター : treeonetreeone
1 ProblemId : 3333 / 出題時の順位表
問題文最終更新日: 2019-10-18 14:17:01

問題文

長さ $N$ の数列 $A$ があり, どの $2$ つの要素も互いに異なります。

次の操作をちょうど $1$ 回行います。

  1. $L$ 以上 $R$ 以下の整数 $x$ を選ぶ。
  2. 数列のすべての要素を $A_i\ \mathrm{XOR}\ x$ に置き換える。

$\mathrm{XOR}$ はビットごとの排他的論理和を表します。

操作によって数列を単調増加にする $x$ は何通りあるか求めてください。 ここで単調増加とはすべての $i(1 \leq i \lt N)$ について $A_i \lt A_{i+1}$ が成立することをいいます。

入力

$N$ $L$ $R$
$A_1$ $A_2$ $\cdots$ $A_N$
  • $1 \leq N \leq 2 \times 10^5$
  • $0 \leq L \leq R \lt 2^{61}$
  • $0 \leq A_i \lt 2^{61}$
  • $i \neq j$ ならば $A_i \neq A_j$
  • 入力はすべて整数

出力

$1$ 行に答えを出力してください。

サンプル

サンプル1
入力
6 1325 1350
1332 1335 1334 1329 1328 1331
出力
4

例えば $x = 1333$ としたとき操作後の数列は $\{1, 2, 3, 4, 5, 6\}$ となり, この数列は単調増加です。

一方で, 例えば $x = 1334$ としたとき操作後の数列は $\{2, 1, 0, 7, 6, 5\}$ となり, この数列は単調増加ではありません。

サンプル2
入力
4 100 500
1 7 41 23
出力
0

数列を単調増加にする $x$ が $1$ つも存在しない場合もあります。

サンプル3
入力
1 0 10000
1
出力
10001

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