No.911 ラッキーソート
レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限
: 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 100
作問者 :
ei1333333
/ テスター :
treeone
タグ : / 解いたユーザー数 100
作問者 :
ei1333333
/ テスター :
treeone
問題文最終更新日: 2019-10-18 14:17:01
問題文
長さ $N$ の数列 $A$ があり, どの $2$ つの要素も互いに異なります。
次の操作をちょうど $1$ 回行います。
- $L$ 以上 $R$ 以下の整数 $x$ を選ぶ。
- 数列のすべての要素を $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、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。