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)$。