{"raw_statement":[{"iden":"statement","content":"Vasya has the sequence consisting of _n_ integers. Vasya consider the pair of integers _x_ and _y_ _k-interesting_, if their binary representation differs from each other exactly in _k_ bits. For example, if _k_ = 2, the pair of integers _x_ = 5 and _y_ = 3 is _k-interesting_, because their binary representation _x_\\=_101_ and _y_\\=_011_ differs exactly in two bits.\n\nVasya wants to know how many pairs of indexes (_i_, _j_) are in his sequence so that _i_ < _j_ and the pair of integers _a__i_ and _a__j_ is _k-interesting_. Your task is to help Vasya and determine this number."},{"iden":"input","content":"The first line contains two integers _n_ and _k_ (2 ≤ _n_ ≤ 105, 0 ≤ _k_ ≤ 14) — the number of integers in Vasya's sequence and the number of bits in which integers in _k-interesting_ pair should differ.\n\nThe second line contains the sequence _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 104), which Vasya has."},{"iden":"output","content":"Print the number of pairs (_i_, _j_) so that _i_ < _j_ and the pair of integers _a__i_ and _a__j_ is _k-interesting_."},{"iden":"examples","content":"Input\n\n4 1\n0 3 2 1\n\nOutput\n\n4\n\nInput\n\n6 0\n200 100 100 100 200 200\n\nOutput\n\n6"},{"iden":"note","content":"In the first test there are 4 _k-interesting_ pairs:\n\n*   (1, 3),\n*   (1, 4),\n*   (2, 3),\n*   (2, 4).\n\nIn the second test _k_ = 0. Consequently, integers in any _k-interesting_ pair should be equal to themselves. Thus, for the second test there are 6 _k-interesting_ pairs:\n\n*   (1, 5),\n*   (1, 6),\n*   (2, 3),\n*   (2, 4),\n*   (3, 4),\n*   (5, 6)."}],"translated_statement":[{"iden":"statement","content":"Vasya 有一个包含 #cf_span[n] 个整数的序列。Vasya 认为一对整数 #cf_span[x] 和 #cf_span[y] 是 _k-有趣的_，如果它们的二进制表示恰好在 #cf_span[k] 个比特位上不同。例如，当 #cf_span[k = 2] 时，整数对 #cf_span[x = 5] 和 #cf_span[y = 3] 是 _k-有趣的_，因为它们的二进制表示 #cf_span[x]=_101_ 和 #cf_span[y]=_011_ 恰好在两个比特位上不同。\n\nVasya 想知道在他的序列中有多少对下标 (#cf_span[i], #cf_span[j]) 满足 #cf_span[i < j]，且整数对 #cf_span[ai] 和 #cf_span[aj] 是 _k-有趣的_。你的任务是帮助 Vasya 确定这个数量。\n\n第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[2 ≤ n ≤ 105], #cf_span[0 ≤ k ≤ 14]) —— Vasya 序列中整数的个数以及 _k-有趣的_ 对中整数应不同的比特位数。\n\n第二行包含序列 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 104])，即 Vasya 拥有的序列。\n\n请输出满足 #cf_span[i < j] 且整数对 #cf_span[ai] 和 #cf_span[aj] 是 _k-有趣的_ 的下标对 (#cf_span[i], #cf_span[j]) 的数量。\n\n在第一个测试用例中，有 4 个 _k-有趣的_ 对：\n\n在第二个测试用例中，#cf_span[k = 0]。因此，任何 _k-有趣的_ 对中的整数必须相等。因此，对于第二个测试用例，有 6 个 _k-有趣的_ 对：\n\n"},{"iden":"input","content":"第一行包含两个整数 #cf_span[n] 和 #cf_span[k] (#cf_span[2 ≤ n ≤ 105], #cf_span[0 ≤ k ≤ 14]) —— Vasya 序列中整数的个数以及 _k-有趣的_ 对中整数应不同的比特位数。第二行包含序列 #cf_span[a1, a2, ..., an] (#cf_span[0 ≤ ai ≤ 104])，即 Vasya 拥有的序列。"},{"iden":"output","content":"请输出满足 #cf_span[i < j] 且整数对 #cf_span[ai] 和 #cf_span[aj] 是 _k-有趣的_ 的下标对 (#cf_span[i], #cf_span[j]) 的数量。"},{"iden":"examples","content":"输入\n4 1\n0 3 2 1\n输出\n4\n\n输入\n6 0\n200 100 100 100 200 200\n输出\n6"},{"iden":"note","content":"在第一个测试用例中，有 4 个 _k-有趣的_ 对： (#cf_span[1], #cf_span[3]), (#cf_span[1], #cf_span[4]), (#cf_span[2], #cf_span[3]), (#cf_span[2], #cf_span[4])。在第二个测试用例中，#cf_span[k = 0]。因此，任何 _k-有趣的_ 对中的整数必须相等。因此，对于第二个测试用例，有 6 个 _k-有趣的_ 对： (#cf_span[1], #cf_span[5]), (#cf_span[1], #cf_span[6]), (#cf_span[2], #cf_span[3]), (#cf_span[2], #cf_span[4]), (#cf_span[3], #cf_span[4]), (#cf_span[5], #cf_span[6])。 "}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, k \\in \\mathbb{Z} $ with $ 2 \\leq n \\leq 10^5 $ and $ 0 \\leq k \\leq 14 $.  \nLet $ A = (a_1, a_2, \\dots, a_n) $ be a sequence of integers with $ 0 \\leq a_i \\leq 10^4 $ for all $ i $.\n\n**Constraints**  \n1. $ 2 \\leq n \\leq 10^5 $  \n2. $ 0 \\leq k \\leq 14 $  \n3. $ 0 \\leq a_i \\leq 10^4 $ for all $ i \\in \\{1, \\dots, n\\} $\n\n**Objective**  \nCount the number of unordered pairs $ (i, j) $ such that $ 1 \\leq i < j \\leq n $ and the Hamming distance between the binary representations of $ a_i $ and $ a_j $ is exactly $ k $, i.e.,  \n$$\n\\left| \\left\\{ b \\in \\mathbb{N}_0 \\mid \\text{bit } b \\text{ of } a_i \\neq \\text{bit } b \\text{ of } a_j \\right\\} \\right| = k\n$$  \nEquivalently,  \n$$\n\\text{count} = \\left| \\left\\{ (i,j) \\mid 1 \\leq i < j \\leq n \\text{ and } \\mathrm{popcount}(a_i \\oplus a_j) = k \\right\\} \\right|\n$$","simple_statement":null,"has_page_source":false}