A6141. 「USACO 2024.12 Platinum」All Pairs Similarity
编程题
省选/NOI-
知识点
题目描述
**题目译自 [USACO 2024 December Contest, Platinum](http://usaco.org/index.php?page=dec24results) Problem 1. [All Pairs Similarity](https://usaco.org/index.php?page=viewproblem2&cpid=1452)**
Farmer John 的 $N$（$1\le N\le 5\cdot 10^5$）头奶牛都被分配了一个长度为 $K$ 的非全零位串（$1\le K\le 20$）。不同的奶牛可能被分配到相同的位串。
两个位串的 Jaccard 相似度定义为它们的按位与的结果中 $\texttt{1}$ 的数量除以它们的按位或的结果中 $\texttt{1}$ 的数量。例如，位串 $\texttt{11001}$ 和 $\texttt{11010}$ 的 Jaccard 相似度为 $2/4$。
对于每头奶牛，输出她的位串与每头奶牛（包括她自己）的位串的 Jaccard 相似度之和，对 $10^9+7$ 取模。具体地说，如果总和等于一个有理数 $a/b$，其中 $a$ 和 $b$ 是互质的整数，则输出范围 $[0,10^9+7)$ 内的唯一整数 $x$，使得 $bx-a$ 被 $10^9+7$ 整除。
Farmer John 的 $N$（$1\le N\le 5\cdot 10^5$）头奶牛都被分配了一个长度为 $K$ 的非全零位串（$1\le K\le 20$）。不同的奶牛可能被分配到相同的位串。
两个位串的 Jaccard 相似度定义为它们的按位与的结果中 $\texttt{1}$ 的数量除以它们的按位或的结果中 $\texttt{1}$ 的数量。例如，位串 $\texttt{11001}$ 和 $\texttt{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$ 位二进制表示。
以下 $N$ 行每行包含一个整数 $i\in (0,2^K)$，表示一头奶牛分配到了 $i$ 的 $K$ 位二进制表示。
输出格式
对于每头奶牛输出一行，包含所求的总和，对 $10^9+7$ 取模。
输入输出样例
输入 #1
4 2 1 1 2 3
输出 #1
500000006 500000006 500000005 500000006
说明/提示
- 测试点 2-15：对于每一个 $K\in \{10,15,16,17,18,19,20\}$ 有两个测试点。