{"problem":{"name":"B. Arpa’s obvious problem and Mehrdad’s terrible solution(Hard)","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 < j ≤ ","description_type":"Markdown"},"platform":"Codeforces","limit":{"time_limit":2000,"memory_limit":524288},"difficulty":"None","is_remote":true,"is_sync":true,"sync_url":null,"sign":"CF10118B"},"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.\n\nImmediately, Mehrdad discovered a terrible solution that nobody trusted. Now Arpa needs your help to implement the solution to that problem.\n\nFirst line contains two integers n and x (1 ≤ n ≤ 2·106, 0 ≤ x ≤ 2107) — the number of elements in the array and the integer x.\n\nSecond line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 2107) — the elements of the array. It's guaranteed that .\n\nInput compression : x and ais are given in 32 base numerical system (i.e. \"V\"  = 31, \"H9\"  = 17·32 + 9 = 480).\n\nIt's guaranteed that no number starts with zero in the input.\n\nPrint a single integer: the answer to the problem.\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.\n\n## Input\n\nFirst line contains two integers n and x (1 ≤ n ≤ 2·106, 0 ≤ x ≤ 2107) — the number of elements in the array and the integer x.Second line contains n integers a1, a2, ..., an (1 ≤ ai ≤ 2107) — the elements of the array. It's guaranteed that .Input compression : x and ais are given in 32 base numerical system (i.e. \"V\"  = 31, \"H9\"  = 17·32 + 9 = 480).It's guaranteed that no number starts with zero in the input.\n\n## Output\n\nPrint a single integer: the answer to the problem.\n\n[samples]\n\n## Note\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.","is_translate":false,"language":"English"},{"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 non-negative integers, where each $ a_i \\in \\mathbb{Z}_{\\geq 0} $.  \n\n**Constraints**  \n1. $ 1 \\leq n \\leq 2 \\cdot 10^6 $  \n2. $ 0 \\leq x \\leq 2^{107} $  \n3. $ 1 \\leq a_i \\leq 2^{107} $ for all $ i \\in \\{1, \\dots, n\\} $  \n4. All values $ x $ and $ a_i $ are provided in base-32 representation; convert to base-10 before processing.  \n\n**Objective**  \nCount the number of ordered pairs $ (i, j) $ such that:  \n$$\n1 \\leq i < j \\leq n \\quad \\text{and} \\quad a_i \\oplus a_j = x\n$$  \nwhere $ \\oplus $ denotes the bitwise XOR operation.","is_translate":false,"language":"Formal"}],"meta":{"iden":"CF10118B","tags":[],"sample_group":[],"created_at":"2026-03-03 11:00:39"}}