06750. USACO·全对相似度 未做

注意：本题的内存限制为 512MB，通常限制的 2 倍。

Farmer John 的 $N$（$1\le N\le 5\cdot 10^5$）头奶牛都被分配了一个长度为 $K$ 的非全零位串（$1\le K\le 20$）。不同的奶牛可能被分配到相同的位串。

两个位串的 Jaccard 相似度定义为它们的按位与的结果中 $\text{1}$ 的数量除以它们的按位或的结果中 $\text{1}$ 的数量。例如，位串 $\text{11001}$ 和 $\text{11010}$ 的 Jaccard 相似度为 $2/4$。

对于每头奶牛，输出她的位串与每头奶牛（包括她自己）的位串的 Jaccard 相似度之和，对 $10^9+7$ 取模。具体地说，如果总和等于一个有理数 $a/b$，其中 $a$ 和 $b$ 是互质的整数，则输出范围 $[0,10^9+7)$ 内的唯一整数 $x$，使得 $bx-a$ 被 $10^9+7$ 整除。

输入的第一行包含 $N$ 和 $K$。

以下 $N$ 行每行包含一个整数 $i\in (0,2^K)$，表示一头奶牛分配到了 $i$ 的 $K$ 位二进制表示。

对于每头奶牛输出一行，包含所求的总和，对 $10^9+7$ 取模。

【样例解释】

奶牛们分配到了以下的位串：$[\text{01},\text{01},\text{10},\text{11}]$。

对于第一头奶牛，总和为 $\text{sim}(1,1)+\text{sim}(1,1)+\text{sim}(1,2)+\text{sim}(1,3)=1+1+0+1/2\equiv 500000006(\mathrm{mod}10^9+7)$。

第二头奶牛的位串与第一头奶牛相同，所以她的总和也与第一头奶牛相同。

对于第三头奶牛，总和为 $\text{sim}(2,1)+\text{sim}(2,1)+\text{sim}(2,2)+\text{sim}(2,3)=0+0+1+1/2\equiv 500000005(\mathrm{mod}10^9+7)$。

【数据规模与约定】

• 测试点 2-15：对于每一个 $K\in \{10,15,16,17,18,19,20\}$ 有两个测试点。

供题：Benjamin Qi