No.911 ラッキーソート

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 通常問題
タグ : / 解いたユーザー数 63
作問者 : TaprisちゃんTaprisちゃん / テスター : treeonetreeone
0 ProblemId : 3333 / 出題時の順位表

問題文

長さ $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
提出ページヘ
下のフォームでの入力は、テキストボックスにフォーカスがない場合は、(Onにしている場合)ショートカットキー・スマートサブミットの影響を受けるので、必要なら提出ページに遷移してください。

言語
問題によって提出できない言語があります。参考
ソースコード
ソースコードのテキストボックスに文字がある場合はファイルは無視されます。
テキストボックスで提出するとCR(\r)が除去されますが、ファイルで提出すると除去されません。