前几天做 arc 时连做两道高维前缀和，今天去看 dp 题单时发现这东西居然叫 sos dp，来刷一下板子。
粘一篇 找到的 blog，感觉引入那里非常自然！
给定一个长度为 \(n\) 的序列，求选出一个子序列，这些数按位与为 \(0\) 的方案数。
\(n,a_i \leq 2^{20}\)
首先显然正着不好做。数字太多了，按位与的信息量也很大，明显不可能存下来，因此要反着做。可以考虑的是反演或容斥。
现在尝试钦定一些位为 \(1\)。则根据容斥原理能写出 \(ans = \sum 2^{f(S)} \cdot (-1)^{|S|}\)，其中 \(f(S)\) 代表钦定集合 \(S\) 中的位为 \(1\) 时的方案数。
