#XMOJ12794. 幸运排序
幸运排序
说明
时间限制:1 Sec
内存限制:256 MB
输入文件:sort.in 输出文件:sort.out
给定长度为 $N$ 的数列 $A$,所有元素互不相同。
你必须恰好执行一次下面的操作:
1. 选出一个整数 $x$,满足 $L \le x \le R$
2. 将数列所有元素替换成 $A_i \ \mathrm{XOR}\ x$
求:有多少个 $x$,可以使得操作之后的数列严格单调递增。
严格单调递增的定义:对所有 $1\le i<N$,满足 $A_i < A_{i+1}$。
输入格式
第一行三个整数 $N,L,R$。
第二行 $N$ 个整数 $A_1,A_2,\cdots,A_N$。
输出格式
输出满足条件的 $x$ 的数量。
样例
样例 1
6 1325 1350
1332 1335 1334 1329 1328 1331
4
样例说明:
例如取 ,操作后得到 ,严格递增;取 得到 ,不满足。
样例 2
4 100 500
1 7 41 23
0
样例说明:
不存在合法的 。
样例 3
1 0 10000
1
10001
样例说明:
时,任意 都合法,一共 个。
数据范围
对于 40% 的数据,$N \le 50$。
对于 100% 的数据,$1 \le N \le 2\times 10^5$,$0 \le L \le R < 2^{61}$,$0 \le A_i < 2^{61}$,$i\neq j$ 时 $A_i \neq A_j$。
相关
在下列比赛中: