English · Original
Chinese · Translation
Formal · Original
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.
Vasya 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.
## Input
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.
The second line contains the sequence _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ ≤ 104), which Vasya has.
## Output
Print the number of pairs (_i_, _j_) so that _i_ < _j_ and the pair of integers _a__i_ and _a__j_ is _k-interesting_.
[samples]
## Note
In the first test there are 4 _k-interesting_ pairs:
* (1, 3),
* (1, 4),
* (2, 3),
* (2, 4).
In 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:
* (1, 5),
* (1, 6),
* (2, 3),
* (2, 4),
* (3, 4),
* (5, 6).
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_ 恰好在两个比特位上不同。
Vasya 想知道在他的序列中有多少对下标 (#cf_span[i], #cf_span[j]) 满足 #cf_span[i < j]，且整数对 #cf_span[ai] 和 #cf_span[aj] 是 _k-有趣的_。你的任务是帮助 Vasya 确定这个数量。
第一行包含两个整数 #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 拥有的序列。
请输出满足 #cf_span[i < j] 且整数对 #cf_span[ai] 和 #cf_span[aj] 是 _k-有趣的_ 的下标对 (#cf_span[i], #cf_span[j]) 的数量。
在第一个测试用例中，有 4 个 _k-有趣的_ 对：
在第二个测试用例中，#cf_span[k = 0]。因此，任何 _k-有趣的_ 对中的整数必须相等。因此，对于第二个测试用例，有 6 个 _k-有趣的_ 对：
## Input
第一行包含两个整数 #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 拥有的序列。
## Output
请输出满足 #cf_span[i < j] 且整数对 #cf_span[ai] 和 #cf_span[aj] 是 _k-有趣的_ 的下标对 (#cf_span[i], #cf_span[j]) 的数量。
[samples]
## Note
在第一个测试用例中，有 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])。
**Definitions**
Let $ n, k \in \mathbb{Z} $ with $ 2 \leq n \leq 10^5 $ and $ 0 \leq k \leq 14 $.
Let $ A = (a_1, a_2, \dots, a_n) $ be a sequence of integers with $ 0 \leq a_i \leq 10^4 $ for all $ i $.
**Constraints**
1. $ 2 \leq n \leq 10^5 $
2. $ 0 \leq k \leq 14 $
3. $ 0 \leq a_i \leq 10^4 $ for all $ i \in \{1, \dots, n\} $
**Objective**
Count 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.,
$$
\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
$$
Equivalently,
$$
\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|
$$
API Response (JSON)
{
"problem": {
"name": "D. k-Interesting Pairs Of Integers",
"description": {
"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 exam",
"description_type": "Markdown"
},
"platform": "Codeforces",
"limit": {
"time_limit": 2000,
"memory_limit": 262144
},
"difficulty": "None",
"is_remote": true,
"is_sync": true,
"sync_url": null,
"sign": "CF769D"
},
"statements": [
{
"statement_type": "Markdown",
"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 exam...",
"is_translate": false,
"language": "English"
},
{
"statement_type": "Markdown",
"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_...",
"is_translate": true,
"language": "Chinese"
},
{
"statement_type": "Markdown",
"content": "**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...",
"is_translate": false,
"language": "Formal"
}
]
}