#2534. 「CQOI2018」异或序列

内存限制:256 MiB 时间限制:1000 ms 标准输入输出
题目类型:传统 评测方式:文本比较
上传者: luyanaa

题目描述

已知一个长度为 n 的整数数列 a_1,a_2,\dots,a_n ,给定查询参数 l r ,问在 a_l,a_{l+1},\dots,a_r 区间内,有多少子序列满足异或和等于 k 。也就是说,对于所有的 x,y ( l \le x \le y \le r) ,满足 a_x \oplus a_{x+1} \oplus \dots \oplus a_y=k x,y 有多少组。

输入格式

输入第一行为 3 个整数 n,m,k

第二行为空格分开的 n 个整数,即 a_1,a_2,\dots,a_n

接下来 m 行,每行两个整数 l_j,r_j ,代表一次查询。

输出格式

输出共 m 行,对应每个查询的计算结果。

样例

样例输入

4 5 1
1 2 3 1
1 4
1 3
2 3
2 4
4 4

样例输出

4
2
1
2
1

数据范围与提示

对于 30\% 的数据, 1 \le n,m \le 1000
对于 100\% 的数据, 1 \le n,m \le 10^5 , 0 \le k,a_i \le 10^5 , 1 \le l_j \le r_j \le n