A6073. 「CQOI2018」异或序列
编程题
提高+/省选-
知识点
题目描述
已知一个长度为 $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$ ，代表一次查询。
第二行为空格分开的 $n$ 个整数，即 $a_1,a_2,\dots,a_n$ 。
接下来 $m$ 行，每行两个整数 $l_j,r_j$ ，代表一次查询。
输出格式
输出共 $m$ 行，对应每个查询的计算结果。
输入输出样例
输入 #1
4 5 1 1 2 3 1 1 4 1 3 2 3 2 4 4 4
输出 #1
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$ 。
对于 $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$ 。