F. Friends and Pizza 详细题解

问题理解

有 $n$ 个披萨（$n \le 20$），第 $i$ 个披萨有 $a_i$ 片。有 $m$ 个朋友（$m \le 5\times 10^5$），每个朋友喜欢某些披萨（用字母表示）。

要选择恰好两个朋友邀请。对于每个披萨：

• 若两人都不喜欢 → Monocarp 吃掉全部 $a_i$ 片
• 若恰好一人喜欢 → 该朋友吃掉全部 $a_i$ 片
• 若两人都喜欢 → 若 $a_i$ 为偶数，每人吃 $a_i/2$ 片；若 $a_i$ 为奇数，两人争吵（这种方案不计入答案）

要求：计算对于每个 $k$，有多少种选两个朋友的方式，使得不争吵且 Monocarp 恰好吃掉 $k$ 片。

---

核心难点

• $n$ 很小（$\le 20$），但 $m$ 很大（$5\times10^5$）
• 直接枚举所有 $\binom{m}{2}$ 对朋友不可行
• 争吵只发生在两人都喜欢某个奇数片披萨时
• Monocarp 吃的片数 = 两人都不喜欢的披萨的片数之和

---

第一步：用位掩码表示喜欢集合

将 $n$ 个披萨编号 $0$ 到 $n-1$（对应字母 $A$ 到第 $n$ 个字母）。
每个朋友的喜欢集合可以用一个 $n$ 位二进制掩码 $mask$ 表示：第 $i$ 位为 $1$ 表示喜欢披萨 $i$。

输入中 $s_i$ 已按字典序排序，但只需转换成掩码。

设 $cnt[mask]$ = 喜欢集合恰好为 $mask$ 的朋友数量。

---

第二步：争吵条件

设两个朋友的掩码分别为 $x$ 和 $y$。
他们不争吵当且仅当：不存在一个披萨 $i$，使得 $a_i$ 为奇数，并且 $x$ 和 $y$ 都包含 $i$。

定义奇数披萨掩码：

$$oddMask = \sum_{i: a_i \text{ 为奇数}} 2^i$$

则不争吵条件等价于：

$$(x \& y) \ \&\ oddMask = 0$$

即 $x$ 和 $y$ 在奇数披萨位上不能同时为 $1$。

---

第三步：Monocarp 吃的片数

Monocarp 吃的披萨 = 两人都不喜欢的披萨 = 全集去掉 $x \cup y$ 对应的披萨。

设 $U = \{0,1,\dots,n-1\}$ 为全集。
两人都不喜欢的披萨集合为 $U \setminus (x \cup y)$，对应的掩码为：

$$fullMask = (2^n - 1) \ \&\ \sim(x | y)$$

Monocarp 吃的片数 = $\sum_{i \notin (x \cup y)} a_i$。

设 $sum[mask] = \sum_{i \in mask} a_i$（即掩码对应披萨的总片数），则：

$$k = sum[fullMask] = totalSlices - sum[x | y]$$

其中 $totalSlices = \sum_{i=0}^{n-1} a_i$。

因此，给定 $x$ 和 $y$，$k$ 由 $x|y$ 唯一确定。

---

第四步：转化为计数问题

设 $F[mask]$ = 满足 $x|y = mask$ 且 $(x \& y) \& oddMask = 0$ 的无序对 $(x,y)$ 的数量（注意 $x$ 和 $y$ 是掩码，不是朋友索引，需要乘以朋友计数）。

对每个掩码 $mask$，$sum[mask]$ 已知，则：

$$k = totalSlices - sum[mask]$$

该 $k$ 对应的答案增加 $F[mask]$。

---

第五步：如何计算 $F[mask]$？

定义 $c[t][mask]$ = 喜欢集合为 $mask$ 且奇数披萨位个数为 $t$ 的朋友数量。
设 $oddCnt[mask] = popcount(mask \& oddMask)$，则 $c[oddCnt[mask]][mask] = cnt[mask]$。

对每个 $t$，对 $c[t]$ 做SOS DP（子集和变换）：

$$C_t[mask] = \sum_{sub \subseteq mask} c[t][sub]$$

$C_t[mask]$ 表示“所有子集包含在 $mask$ 内且奇数披萨位个数为 $t$ 的朋友总数”。

---

第六步：卷积得到对 $(x,y)$ 的计数

对于固定的 $x$ 和 $y$，$x \cup y = mask$ 且 $x \& y$ 与 $oddMask$ 无交。

设 $u = x \& y$，$v = x \oplus y$（对称差），则 $mask = u \cup v$，且 $u \& oddMask = 0$。
更简单的做法：固定 $mask$，枚举 $u \subseteq mask$ 且 $u \& oddMask = 0$，则 $v = mask \setminus u$，且 $x$ 和 $y$ 由 $(u,v)$ 拆分成两个集合：$x = u \cup p$，$y = u \cup q$，其中 $p \cup q = v$，$p \cap q = \varnothing$，且 $p,q$ 可以是空集，且 $p,q \subseteq v$。
但这会引入 $2^{|v|}$ 的拆分，不可行（$n=20$ 太大）。

---

标程使用的巧妙方法

标程计算 $B[k][mask]$：

$$B[k][mask] = \sum_{i+j = k} C_i[mask] \cdot C_j[mask] $$

其中 $C_i[mask]$ 是 SOS DP 后的结果。

然后对 $B[k]$ 做逆 SOS DP，得到 $b[k][mask]$，其中 $b[k][mask]$ 表示“所有无序对 $(x,y)$ 满足 $x \cup y = mask$ 且 $oddCnt[x] + oddCnt[y] = k$”的数量。

因为 $oddCnt[x] + oddCnt[y] = oddCnt[x \cup y] + oddCnt[x \& y]$，结合不争吵条件 $oddCnt[x \& y] = 0$，所以 $oddCnt[x] + oddCnt[y] = oddCnt[x \cup y]$。

因此 $k$ 就是 $oddCnt[mask]$。
所以 $b[oddCnt[mask]][mask]$ 恰好是“无序对 $(x,y)$ 满足 $x \cup y = mask$ 且不争吵”的数量，即 $F[mask]$。

---

第七步：减去 $x = y$ 的情况

当前 $F[mask]$ 包含了 $x = y$ 的情况（即同一个朋友选两次），但题目要求选两个不同的朋友。
需要减去 $x = y$ 的贡献：当 $mask = x$ 且 $(x \& x) \& oddMask = x \& oddMask = 0$ 时，$x$ 自身对 $F[mask]$ 贡献了 $\binom{cnt[x]}{2}$？
不对，$x = y$ 时，$x \cup y = x$，所以 $mask = x$，且 $x \& oddMask = 0$（不争吵）。此时对 $F[mask]$ 的贡献是 $\binom{cnt[x]}{2}$ 吗？
实际上 $x = y$ 时，对应的无序对是 $(x,x)$，但两个朋友必须是不同的，所以应该完全排除。
标程最后用了一个循环减去 $x = y$ 的贡献：

for(int i = 0; i < (1 << n); i++) {
    if(i & odd_mask) continue;
    int sum = 0;
    for(int j = 0; j < n; j++)
        if((i >> j) & 1)
            sum += a[j];
    ans[sum] -= cnt[i];
}

注意这里减的是 $cnt[i]$，不是 $\binom{cnt[i]}{2}$。为什么？
因为 $B$ 中已经包含了 $x=y$ 的贡献作为乘积项 $cnt[i] \cdot cnt[i]$ 的一部分，但我们需要的是无序对且 $x \neq y$。最后除以 $2$ 之前，$x=y$ 的贡献是 $cnt[i]$（因为 $x=y$ 在 $B$ 中贡献了 $cnt[i] \cdot cnt[i]$，但除以 $2$ 后变成 $cnt[i]^2/2$，减去 $cnt[i]$ 是为了修正）。

---

第八步：最终答案

对每个 $mask$，$F[mask] = b[oddCnt[mask]][mask]$（注意 $b$ 是逆 SOS 后的结果）。
计算 $k = totalSlices - sum[mask]$，将 $F[mask]$ 加到 $ans[k]$ 中。

最后，所有 $ans[k]$ 除以 $2$（因为每个无序对被计算了两次），输出即可。

---

复杂度分析

• SOS DP 对每层 $O(n \cdot 2^n)$，$n \le 20$，$2^n \approx 10^6$，可行
• 卷积部分 $O((oddPizzas+1)^2 \cdot 2^n)$，其中 $oddPizzas \le n \le 20$，约 $400 \times 10^6 = 4\times 10^8$，在 8 秒内可通过（需优化常数）
• 最后遍历 $2^n$ 个掩码，$O(2^n \cdot n)$

---

总结

本题的核心技巧：

1. 用位掩码表示披萨喜欢集合（$n \le 20$）
2. 用 SOS DP 处理子集统计
3. 用卷积合并两个朋友的集合
4. 用逆 SOS DP 恢复出并集信息
5. 通过奇偶性处理争吵条件

这是典型的“子集卷积 + SOS DP”问题，适用于 $n$ 较小但 $m$ 很大的组合计数场景。