### alpenglow's blog

By alpenglow, history, 6 weeks ago,

Given N (N <= 100 000) small sets (size at most 7). find number of non-intersecting pairs among these sets.

•  » » » 6 weeks ago, # ^ |   0 OK. The first approach that came to my mind was inclusion-exclusion over common elements in the set: Add one for every pair of indices $(i, j)$, subtract one for every tuple $(\{x\}, i, j)$ with $x \in A_i \cap A_j$, add one for every tuple $(\{x, y\}, i, j)$ with $x \neq y$ and $\{x, y\} \subseteq A_i \cap A_j$, and so on. But it is clear that only the sets $S$ which are subsets of at least one $A_i$ can contribute to the sum, and there are at most $2^7 \cdot 10^5$ such sets, and the contribution of each to the sum can be maintained using a hash-map: Process the sets in the input one at a time, and for each subset $S \subseteq A_i$, add or subtract as appropriate the number of input sets $A_j$ already encountered with $S \subseteq A_j$.However, with sets of common prime factors of numbers less than $10^6$, there is a natural and obvious perfect hash function: the product, and so an array can be used instead.