B. Arpa’s obvious problem and Mehrdad’s terrible solution

Codeforces

IDCF742B

Time1000ms

Memory256MB

Difficulty—

brute forcemathnumber theory

English · Original

Chinese · Translation

Formal · Original

_There are some beautiful girls in Arpa’s land as mentioned before._ Once Arpa came up with an obvious problem: Given an array and a number _x_, count the number of pairs of indices _i_, _j_ (1 ≤ _i_ < _j_ ≤ _n_) such that , where is bitwise _xor_ operation (see notes for explanation). <center>![image](https://espresso.codeforces.com/dabb26b186836749476e3b172f0e6aef26dcb498.png)</center>Immediately, Mehrdad discovered a terrible solution that nobody trusted. Now Arpa needs your help to implement the solution to that problem. ## Input First line contains two integers _n_ and _x_ (1 ≤ _n_ ≤ 105, 0 ≤ _x_ ≤ 105) — the number of elements in the array and the integer _x_. Second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 105) — the elements of the array. ## Output Print a single integer: the answer to the problem. [samples] ## Note In the first sample there is only one pair of _i_ = 1 and _j_ = 2. so the answer is 1. In the second sample the only two pairs are _i_ = 3, _j_ = 4 (since ) and _i_ = 1, _j_ = 5 (since ). A bitwise _xor_ takes two bit integers of equal length and performs the logical _xor_ operation on each pair of corresponding bits. The result in each position is 1 if only the first bit is 1 or only the second bit is 1, but will be 0 if both are 0 or both are 1. You can read more about bitwise _xor_ operation here: [https://en.wikipedia.org/wiki/Bitwise_operation#XOR](https://en.wikipedia.org/wiki/Bitwise_operation#XOR).

_Arpa 的土地上有一些美丽的女孩，如前所述。_ 有一天，Arpa 提出了一个显而易见的问题：给定一个数组和一个数字 #cf_span[x]，请计算满足条件的索引对 #cf_span[i, j]（#cf_span[1 ≤ i < j ≤ n]）的数量，其中为按位 _xor_ 运算（详见注释解释）。 Mehrdad 立即发现了一个糟糕的解法，但没人信任它。现在 Arpa 需要你帮助实现该问题的正确解法。第一行包含两个整数 #cf_span[n] 和 #cf_span[x]（#cf_span[1 ≤ n ≤ 105, 0 ≤ x ≤ 105]）——数组中元素的个数和整数 #cf_span[x]。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 105]）——数组的元素。请输出一个整数：该问题的答案。在第一个样例中，只有一对 #cf_span[i = 1] 和 #cf_span[j = 2]。因此答案为 #cf_span[1]。在第二个样例中，仅有两对：#cf_span[i = 3], #cf_span[j = 4]（因为）和 #cf_span[i = 1], #cf_span[j = 5]（因为）。按位 _xor_ 对两个等长的二进制整数进行操作，对每一对对应位执行逻辑 _xor_ 运算。若仅第一个位为 #cf_span[1] 或仅第二个位为 #cf_span[1]，则结果为 #cf_span[1]；若两者均为 #cf_span[0] 或均为 #cf_span[1]，则结果为 #cf_span[0]。更多关于按位 _xor_ 运算的信息请参见：https://en.wikipedia.org/wiki/Bitwise_operation#XOR。 ## Input 第一行包含两个整数 #cf_span[n] 和 #cf_span[x]（#cf_span[1 ≤ n ≤ 105, 0 ≤ x ≤ 105]）——数组中元素的个数和整数 #cf_span[x]。第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 105]）——数组的元素。 ## Output 请输出一个整数：该问题的答案。 [samples] ## Note 在第一个样例中，只有一对 #cf_span[i = 1] 和 #cf_span[j = 2]。因此答案为 #cf_span[1]。在第二个样例中，仅有两对：#cf_span[i = 3], #cf_span[j = 4]（因为）和 #cf_span[i = 1], #cf_span[j = 5]（因为）。按位 _xor_ 对两个等长的二进制整数进行操作，对每一对对应位执行逻辑 _xor_ 运算。若仅第一个位为 #cf_span[1] 或仅第二个位为 #cf_span[1]，则结果为 #cf_span[1]；若两者均为 #cf_span[0] 或均为 #cf_span[1]，则结果为 #cf_span[0]。更多关于按位 _xor_ 运算的信息请参见：https://en.wikipedia.org/wiki/Bitwise_operation#XOR。

**Definitions** Let $ n \in \mathbb{Z}^+ $, $ x \in \mathbb{Z}_{\geq 0} $. Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers with $ a_i \in \mathbb{Z}^+ $. **Constraints** 1. $ 1 \leq n \leq 10^5 $ 2. $ 0 \leq x \leq 10^5 $ 3. $ 1 \leq a_i \leq 10^5 $ for all $ i \in \{1, \dots, n\} $ **Objective** Count the number of pairs $ (i, j) $ such that $ 1 \leq i < j \leq n $ and $$ a_i \oplus a_j = x $$ where $ \oplus $ denotes the bitwise XOR operation.

Samples

Input #1

2 3
1 2

Output #1

Input #2

6 1
5 1 2 3 4 1

Output #2

API Response (JSON)

{
  "problem": {
    "name": "B. Arpa’s obvious problem and Mehrdad’s terrible solution",
    "description": {
      "content": "_There are some beautiful girls in Arpa’s land as mentioned before._ Once Arpa came up with an obvious problem: Given an array and a number _x_, count the number of pairs of indices _i_, _j_ (1 ≤ _i",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 1000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF742B"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "_There are some beautiful girls in Arpa’s land as mentioned before._\n\nOnce Arpa came up with an obvious problem:\n\nGiven an array and a number _x_, count the number of pairs of indices _i_, _j_ (1 ≤ _i...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "_Arpa 的土地上有一些美丽的女孩，如前所述。_\n\n有一天，Arpa 提出了一个显而易见的问题：\n\n给定一个数组和一个数字 #cf_span[x]，请计算满足条件的索引对 #cf_span[i, j]（#cf_span[1 ≤ i < j ≤ n]）的数量，其中  为按位 _xor_ 运算（详见注释解释）。\n\nMehrdad 立即发现了一个糟糕的解法，但没人信任它。现在 Arpa 需要你帮助实现...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ n \\in \\mathbb{Z}^+ $, $ x \\in \\mathbb{Z}_{\\geq 0} $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ a_i \\in \\mathbb{Z}^+ $.\n\n**Constraints**  \n1. $ 1 \\le...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments