{"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_ < _j_ ≤ _n_) such that , where is bitwise _xor_ operation (see notes for explanation).\n\n<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.\n\n## Input\n\nFirst line contains two integers _n_ and _x_ (1 ≤ _n_ ≤ 105, 0 ≤ _x_ ≤ 105) — the number of elements in the array and the integer _x_.\n\nSecond line contains _n_ integers _a_1, _a_2, ..., _a__n_ (1 ≤ _a__i_ ≤ 105) — the elements of the array.\n\n## Output\n\nPrint a single integer: the answer to the problem.\n\n[samples]\n\n## Note\n\nIn the first sample there is only one pair of _i_ = 1 and _j_ = 2. so the answer is 1.\n\nIn the second sample the only two pairs are _i_ = 3, _j_ = 4 (since ) and _i_ = 1, _j_ = 5 (since ).\n\nA 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).","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 需要你帮助实现该问题的正确解法。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[x]（#cf_span[1 ≤ n ≤ 105, 0 ≤ x ≤ 105]）——数组中元素的个数和整数 #cf_span[x]。\n\n第二行包含 #cf_span[n] 个整数 #cf_span[a1, a2, ..., an]（#cf_span[1 ≤ ai ≤ 105]）——数组的元素。\n\n请输出一个整数：该问题的答案。\n\n在第一个样例中，只有一对 #cf_span[i = 1] 和 #cf_span[j = 2]。  因此答案为 #cf_span[1]。\n\n在第二个样例中，仅有两对：#cf_span[i = 3], #cf_span[j = 4]（因为 ）和 #cf_span[i = 1], #cf_span[j = 5]（因为 ）。\n\n按位 _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。\n\n## Input\n\n第一行包含两个整数 #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]）——数组的元素。\n\n## Output\n\n请输出一个整数：该问题的答案。\n\n[samples]\n\n## Note\n\n在第一个样例中，只有一对 #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。","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 \\leq n \\leq 10^5 $  \n2. $ 0 \\leq x \\leq 10^5 $  \n3. $ 1 \\leq a_i \\leq 10^5 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCount the number of pairs $ (i, j) $ such that $ 1 \\leq i < j \\leq n $ and  \n$$\na_i \\oplus a_j = x\n$$  \nwhere $ \\oplus $ denotes the bitwise XOR operation.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF742B","tags":["brute force","math","number theory"],"sample_group":[["2 3\n1 2","1"],["6 1\n5 1 2 3 4 1","2"]],"created_at":"2026-03-03 11:00:39"}}