出现了，但发现没写过，故记之。
状压枚举子集
需求：对于 每一个 长度为 \(n\) 的二进制状态 \(s\)，枚举其子状态 \(\{ t \mid t \operatorname{bitand} s = t \}\)。
直接枚举所有长度为 \(n\) 的状态 \(t'\)，然后判定是否满足 \(t' \operatorname{bitand} s = t\)，总时间复杂度是 \(O(2^{2n})\) 的。考虑优化。
考虑对于所有 \(2^n\) 种状态 \(s\)，假如有一种方式能够不重不漏地枚举出它们中每一个的所有子状态，那么总时间复杂度是多少呢？
把所有数对 \((s, t)\) 排列在一起。那么对于 \(n\) 位中的每一位 \(i\)，枚举每一个 \((s', t')\)。
那么存在以下几种可能性：
- \({s'}_i=1,{t'}_i=1\)；
- \({s'}_i=1, {t'}_i=0\)；
- \({s'}_i=0, {t'}_i = 0\)。
假如我们用 \(o_i=0,1,2\) 分别代表第一、二、三种情况，完全可以用长度为 \(n\) 的三进制状态 \(o\) 还原数对 \((s, t)\)。
由于这个 \((s, t)\) 序列中肯定没有完全相同的元素，也就是说，对于每一个 \((s, t)\)，其 \(o\) 都各不相同。
因此，\((s, t)\) 的数目不超过 \(3^n\)。
又因为对于 \(3^n\) 个 \(o\)，每个都可以还原出合法状态，所以总的 \((s, t)\) 数目应恰好为 \(3^n\)。
也就是说，假如有一种方式能够不重不漏地枚举出每一个 \(s\) 的所有子状态 \(t\)，可以做到均摊 \(O(3^n)\)。
接下来探讨这种枚举方式。直接给出结论：
for (int t = s; t; t = (t - 1) & s);其实不难理解。从 \(t\) 的定义出发即 \(t \operatorname{bitand} s = t\)，重点理解 \(t\gets (t - 1)\operatorname{bitand} s\) 这一步。
分两种情况讨论：
\(t-1\) 较 \(t\) 发生退位：
因为只减 \(1\)，所以末位一定发生退位。
如果发生连续退位，一定是因为末端有连续的 \(0\)。对于第一个 \(1\)（记为第 \(j\) 位），已经枚举完了在 \(j\) 及更高位固定在当前状态下的所有状态。
则应有：
- 比 \(j\) 更高的数位，未受到退位带来的连续影响的位不变；
- 第 \(j\) 位 \(1\to 0\)；
- 从第 \(j\) 位一直到末位都有 \(0\to 1\)。
此时与 \(s\) 进行 \(\operatorname{bitand}\)，得到比 \(j\) 更高的数位不变、\(j\) 位 \(1\to 0\)、比 \(j\) 更低的数位变为抵着 \(s\) 对应数位的最大状态。
综上，这是比 \(t\) 小的第一个合法状态。
\(t-1\) 较 \(t\) 不发生退位：
根据上面的讨论，其实就是末位不退位，即末位 \(1\to 0\)。显然是比 \(t\) 更小的第一个合法状态。
综上，实现了从大到小依次枚举合法状态，因此不重不漏。
枚举补集
看了几个比较抽象的博客，但是我觉得不如直接把 \(s\) 异或一下 \(2^n-1\) 然后枚举子集。
高维前缀和
首先理解一下什么是高维前缀和。实际上全程应为边长为 \(2\) 的高维空间前缀和。
传统的二位前缀和使用容斥求解，很难扩展到高维。如果我们取 \(n=2\)，那么有另一种无需容斥位运算求解方式：
- 对于一维前缀和，其计算方式为 \(s_1=s_0+a_1\)；
- 对于二维前缀和，其计算方式为 \(s_{(11)_2}=s_{(00)_2}+s_{(01)_2}+s_{(10)_2}+a_{(11_2)}\)，以此类推。
即在 \(n=2\) 的情况下，我们发现我们可以将 \(k\) 维前缀和看作在 \(k\) 位二进制数上做子集元素求和。显然根据枚举子集有 \(3^k\) 的做法，但还能更快。