CF769D k-Interesting Pairs Of Integers

Vasya 有一个由 $n$ 个整数组成的序列。如果两个整数 $x$ 和 $y$ 的二进制表示恰好有 $k$ 位不同，则 Vasya 认为这对整数是 $k$-有趣的。例如，如果 $k=2$，则 $x=5$ 和 $y=3$ 是 $k$-有趣的，因为 $x=101$ 和 $y=011$ 在二进制表示中恰好有两位不同。 Vasya 想知道，在他的序列中，有多少对下标 $(i,j)$ 满足 $i

第一行包含两个整数 $n$ 和 $k$（$2 \leq n \leq 10^5$，$0 \leq k \leq 14$），分别表示 Vasya 的序列中的整数个数和 $k$-有趣对的不同比特位数量。 第二行包含 $n$ 个整数 $a_1,a_2,\ldots,a_n$（$0 \leq a_i \leq 10^4$），表示 Vasya 的序列。

输出一个整数，表示有多少对 $(i,j)$ 满足 $i

在第一个样例中，有 4 个 $k$-有趣的对： - $(1,3)$， - $(1,4)$， - $(2,3)$， - $(2,4)$。 在第二个样例中，$k=0$。因此，$k$-有趣的整数对中的两个数必须完全相等。在第二个样例中，有 6 个 $k$-有趣的对： - $(1,5)$， - $(1,6)$， - $(2,3)$， - $(2,4)$， - $(3,4)$， - $(5,6)$。 由 ChatGPT 5 翻译