异或与最爱数字(XOR and Favorite Number)

题目描述

Bob 有一个最喜欢的数字 $k$，以及一个长度为 $n$ 的数组 $a_{i}$。现在他要求你回答 $m$ 个询问。每个询问由一对 $l_{i}$ 和 $r_{i}$ 给出，问你在区间 $l \leq i \leq j \leq r$ 内，有多少组整数对 $(i,j)$，使得数列 $a_{i}, a_{i+1}, \ldots, a_{j}$ 的异或和等于 $k$。

输入格式

输入的第一行包含三个整数 $n$、$m$ 和 $k$（$1 \leq n, m \leq 100000$，$0 \leq k \leq 1000000$）——数组的长度、询问的数量和 Bob 最喜欢的数字。

第二行包含 $n$ 个整数 $a_{i}$（$0 \leq a_{i} \leq 1000000$）——Bob 的数组。

接下来的 $m$ 行每行包含两个整数 $l_{i}$ 和 $r_{i}$（$1 \leq l_{i} \leq r_{i} \leq n$），表示第 $i$ 个询问的参数。

输出格式

输出 $m$ 行，按照输入顺序依次输出每个询问的答案。

样例输入 #1

6 2 3
1 2 1 1 0 3
1 6
3 5

样例输出 #1

7
0

样例输入 #2

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

样例输出 #2

9
4
4

数据范围

在第一个样例中，第一个询问中满足条件的 $(i,j)$ 对有：$(1,2)$、$(1,4)$、$(1,5)$、$(2,3)$、$(3,6)$、$(5,6)$、$(6,6)$。第二个询问中不存在满足条件的 $(i,j)$ 对。

在第二个样例中，所有长度为奇数的子数组的异或值都是 $1$。

由 ChatGPT 5 翻译

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1800。

测试点分布

出处：原题链接