随记 – 二月二十四日 – 一个集合的子集的子集数之和

有集合$S$，$|S|=n$，则有$$\sum\limits_{T \subseteq S}2^{|T|}=\sum\limits_{k=0}^{n}2^k\dbinom{n}{k}=3^n$$。因此，若我们枚举集合，枚举集合的子集的子集做状压DP时，可以得到正确的复杂度$\mathrm{O}(3^n)$而非错误的$\mathrm{O}(2^n\times 2^n)=\mathrm{O}(4^n)$。参见AtCoder ABC 187 F – Close Group。

可以这样证明：考虑某个子集的子集$P \subseteq T \subseteq S$，则$S$中的每个元素有三种状态：$a\in P$，$a \notin P, a \in T$，$a \notin T, a \in S$。显然这样可以唯一表示$S$，$T$以及$P$，对应了所有子集的拆分方案。故原式成立。