Tutorial for CF1641D

· · 题解

赛时听到 jly 二分加容斥做完了，非常厉害，当时我还只会口胡一个随机化。

讲一讲两个做法。一个是 bitset 平衡复杂度，一个是 Hash/Trie 双指针维护答案。友情 @7kbyte（

Solution 1

bitset 的做法看上去似乎比较显然。对于 O(n\times m) 种权值，每种权值开一个 n 位的 bitset，表示权值 c 是否出现在第 i 个数组中。将 n 个数组以 w_i 为关键字从小到大排序，枚举数组对 (i,j) 中的 j，找一个最小的 i 与之匹配，怎么做呢？可以将数组 j 内的元素的 bitset 或起来并反转每个位，然后找最低位的 1 的位置。时间复杂度与空间复杂度均为 O\left(\frac{n^2m}{\omega}\right)，不过空间复杂度太大了过不去。考虑 trivial 的平衡复杂度，对于出现次数 <B 的权值不再对其维护 bitset，而是直接暴力。时间复杂度为 O\left(nmB+\frac{n^2}{\omega}\max\left(m,\frac{n}{B}\right)\right)，空间复杂度为 O\left(\frac{n^2}{\omega B}\right)，平衡一下可得 B \approx \sqrt{\frac{n^2}{m\omega}}，空间复杂度变为 O\left(\sqrt{\frac{n^2m}{\omega}}\right)。

Solution 2

Hash/Trie 的做法则基于容斥。

双指针的性质特别显然，问题其实是如何快速找出当前是否存在不交的数组对。

分别写出数组 A,B 的幂集 P_A,P_B。

对下列式子求值

\sum_{a\in P_A}\sum_{b\in P_B}[a=b](-1)^{|a|-1}

若 A,B 存在交集，上式值必然为 1，否则为 0。

设 A 与 B 交集大小为 s，考虑这个式子其实求的是

\binom{s}{1}-\binom{s}{2}+\binom{s}{3}\dots

于是显然。

怎么判断子集相同？想到可以用 Hash 来处理一个集合的子集。具体来说，对于每个数组求出其子集的 Hash 值。然后两两比对判断当前是否存在不交的数组对么？只需要开一个桶在可能的答案区间发生变化的时候（即双指针移动时）统计上式的贡献即可，若在删除一个数组的贡献之后上式的总贡献没有变化，说明这个数组是不交的数组对的一个元素。

Trie 的做法只是将 Hash 和桶换掉了，仍然是维护上式的总贡献，本质没有发生变化。

时间复杂度为 O(n2^m)。