题目解法分析

问题重述

有 $N$ 个长度为 $K$ 的非全零位串（$K \le 20$），定义两个位串 $x$ 和 $y$ 的 Jaccard 相似度 为： [ \text{sim}(x, y) = \frac{\text{popcount}(x & y)}{\text{popcount}(x | y)} ] 其中 $\text{popcount}$ 表示二进制中 $1$ 的个数。

对于每个位串 $x$，计算它与所有位串（包括自身）的 Jaccard 相似度之和，结果对 $10^9+7$ 取模。

算法思路

1. 关键公式变换

对于两个位串 $x$ 和 $y$，设：

• $a = \text{popcount}(x \& y)$（按位与中 $1$ 的个数）
• $b = \text{popcount}(x | y)$（按位或中 $1$ 的个数）

由集合论恒等式： [ \text{popcount}(x | y) = \text{popcount}(x) + \text{popcount}(y) - \text{popcount}(x & y) ]

因此： [ \text{sim}(x, y) = \frac{a}{\text{popcount}(x) + \text{popcount}(y) - a} ]

2. 问题转化

对于固定的 $x$，我们需要计算： [ \sum_{y} \frac{\text{popcount}(x & y)}{\text{popcount}(x) + \text{popcount}(y) - \text{popcount}(x & y)} ]

设 $p = \text{popcount}(x)$，$q = \text{popcount}(y)$，$a = \text{popcount}(x \& y)$。

则： [ \text{sim}(x, y) = \frac{a}{p + q - a} ]

3. 按交集大小分组

对于固定的 $x$ 和交集大小 $j = \text{popcount}(x \& y)$，我们需要知道有多少个 $y$ 满足 $\text{popcount}(x \& y) = j$。

但是直接计算这个很困难，因为 $j$ 依赖于 $x$ 和 $y$ 的交集。

4. 高维前缀和技巧

代码使用了 高维前缀和（SOS DP） 来计算：

• 第一次：$f[mask][k]$ 表示有多少个位串 $y$ 满足 $\text{popcount}(mask \& y) = k$
• 第二次：$f[mask][k]$ 表示有多少个位串 $y$ 满足 $\text{popcount}(mask \& y) = k$，并且乘以 $\text{popcount}(y)$

5. 最终计算

对于每个 $x$，枚举交集大小 $j$：

• 第一部分：$\sum_j \frac{j}{p + q - j} \times \text{count}_j$
• 第二部分：$\sum_j \frac{1}{p + q - j} \times (\text{count}_j \times q)$

其中 $\text{count}_j$ 是满足 $\text{popcount}(x \& y) = j$ 的 $y$ 的数量。

代码中通过两次高维前缀和分别计算这两部分。

算法步骤

1. 预处理

   • 计算每个位串的 $\text{popcount}$
   • 预处理模逆元 $\text{inv}[i]$ 用于除法

2. 第一次高维前缀和

   • 初始化 $f[mask][\text{popcount}(mask)] = \text{cnt}[mask]$
   • 通过高维前缀和计算 $f[mask][k]$ 表示有多少个 $y$ 满足 $\text{popcount}(mask \& y) = k$

3. 第二次高维前缀和

   • 初始化 $f[mask][\text{popcount}(mask)] = \text{cnt}[mask] \times \text{popcount}(mask)$
   • 同样计算高维前缀和

4. 合并结果

   • 对于每个 $x$，枚举交集大小 $j$
   • 计算：$\text{ans}[x] = \sum_j \left( \frac{j \times (p - j) + q}{p + q - j} \right) \times \text{count}_j$
   • 其中 $p = \text{popcount}(x)$，$q = \text{popcount}(y)$

复杂度分析

• 高维前缀和：$O(K \cdot 2^K \cdot K) = O(K^2 \cdot 2^K)$
• 由于 $K \le 20$，$2^K \approx 10^6$，可以接受
• 总复杂度：$O(K^2 \cdot 2^K + N)$

算法标签

• 高维前缀和（SOS DP）
• 位运算技巧
• 组合计数
• 模逆元
• 包含排除原理

这个解法通过高维前缀和高效计算所有位串对之间的交集信息，再结合数学变换将 Jaccard 相似度求和问题转化为可计算的形式，是一个典型的位运算+组合计数题目。