出现了,但发现没写过,故记之。
状压枚举子集
需求:对于 每一个 长度为 \(n\) 的状态 \(s\),枚举其子状态 \(\{ t \mid t \operatorname{bitand} s = t \}\)。
直接枚举所有长度为 \(n\) 的状态 \(t'\),然后判定是否满足 \(t' \operatorname{bitand} s = t\),总时间复杂度是 \(\mathcal 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\),可以做到均摊 \(\mathcal 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\) 然后枚举子集。
高维前缀和
首先考虑一下什么是高维前缀和。
理解起来的困难点在于这个命名方式虽然和一维 / 二维前缀和相似,但其内涵有较大区别。