← 返回题目列表

Codeforces · 742/B

B. Arpa 的明显问题和 Mehrdad 糟糕的解决方案

中文机器翻译题面 查看原题

如前所述,阿尔帕的土地上有一些美丽的女孩。

有一次Arpa提出了一个明显的问题:

给定一个数组和一个数字 x,计算索引 i、j (1 ≤ i < j ≤ n) 的对数,使得 $$a_i \oplus a_j = x$$,其中 $$\bigcirc$$ 是按位异或运算(请参阅注释以了解解释)。

Mehrdad 立即发现了一个没人信任的糟糕解决方案。现在 Arpa 需要您的帮助来实施该问题的解决方案。

输入

第一行包含两个整数 n 和 x (1 ≤ n ≤ 105, 0 ≤ x ≤ 105) - 数组中元素的数量和整数 x。

第二行包含 n 个整数 a1, a2, ..., an (1 ≤ ai ≤ 105) - 数组的元素。

输出

打印单个整数:问题的答案。

示例

输入 #1

2 3
1 2

输出 #1

1

输入 #2

6 1
5 1 2 3 4 1

输出 #2

2

注意

在第一个样本中只有一对 i = 1 和 j = 2。 $$a_{1} \oplus a_{2} = 3 = x$$ 所以答案是 1。

在第二个样本中,仅有的两对是 i = 3, j = 4(因为 $$2 \oplus 3 = 1$$)和 i = 1, j = 5(因为 $$5 \oplus 4 = 1$$)。

按位异或采用两个长度相等的位整数,并对每对对应位执行逻辑异或运算。如果只有第一位为 1 或只有第二位为 1,则每个位置的结果为 1,但如果两者均为 0 或均为 1,则结果为 0。您可以在此处阅读有关按位异或运算的更多信息:https://en.wikipedia.org/wiki/Bitwise_operation#XOR。