by TheBigYellowDuck
相关链接：[[状态压缩]]
前置知识
高维前缀和是一类解决子集问题的方法。
考虑二维前缀和
\[S(i,j)=S(i-1,j)+S(i,j-1)-S(i-1,j-1)-a_{i,j} \]但是这么容斥，在维数很高的时候会很复杂。
我们考虑另一种求法：
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] += a[i - 1][j];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
a[i][j] += a[i][j - 1];
这样也能达到求前缀和的效果。这样的前缀和是由零维到一维再到二维累加起来的。
同理，考虑三维前缀和。
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
a[i][j][k] += a[i - 1][j][k];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
a[i][j][k] += a[i][j - 1][k];
for (int i = 1; i <= n; i++)
for (int j = 1; j <= n; j++)
for (int k = 1; k <= n; k++)
a[i][j][k] += a[i][j][k - 1];
对于高维前缀和，我们令集合 \(S\) 的大小为它的维数，那么从 \(|S|-1\) 维前缀和推到 \(|S|\) 维前缀和就是这样的。
for (int j = 0; j < n; j++)
for (int i = 0; i < (1 << n); i++)
if (i >> j & 1)
f[i] += f[i ^ (1 << j)];
应用在子集问题中，这样做的时间复杂度为 \(\mathcal{O}(n2^n)\)，比暴力枚举子集的 \(\mathcal{O}(3^n)\) 要优秀。
同时，如果做高维后缀和，相当于求超集的答案。
for (int j = 0; j < n; j++)
for (int i = 0; i < (1 << n); i++)
if ((i >> j & 1) == 0)
f[i] += f[i | (1 << j)];
ARC100E Or Plus Max
很奇妙的一道题。
\(i\operatorname{or}j\leq k\) 很奇怪，考虑转化为 \(i\operatorname{or}j=k\) 的答案，求前缀最大值即可。
\(i\operatorname{or}j=k\) 还是很不好，考虑转化为 \(i,j\subseteq k\)。这样的 \(i,j\) 一定满足 \(i\operatorname{or}j\leq k\)，也是合法的。
这样就变成正常的子集问题了。用高维前缀和维护每个集合的最大值和次大值即可。
时间复杂度 \(\mathcal{O}(n2^n)\)。
Submission #46181257 - AtCoder Regular Contest 100
CF449D Jzzhu and Numbers
考虑容斥。先建出容斥模型。
- 每个元素为一种选取方案。全集 \(U\) 为所有选取方案构成的集合。
- 元素 \(A\) 的第 \(i\) 种属性为 \(a\in A\) 按位与之和的二进制第 \(i\) 位上为 \(0\)。
- \(S_i\) 为具有第 \(i\) 种属性的元素构成的集合。
设二进制最高位为 \(m\)，我们要求的就是
\[\left|\bigcap_{i=1}^m S_i\right| \]对这个东西容斥一下。
\[\left|\bigcap_{i=1}^m S_i\right|=|U|+\sum_{k=1}^m(-1)^k\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^k\overline{S_{a_i}}\right| \]这里的 \(\overline {S_i}\) 就是按位与之和第 \(i\) 位上为 \(1\) 的选取方案的集合。
枚举二进制集合 \(S\)，要求 \(i\in S\) 位上都为 \(1\) 的选取方案数，相当于求按位与之和包含 \(S\) 的选取方案数。而按位与之和包含 \(S\)，又要求每个数都包含 \(S\)。
设 \(f(S)\) 为包含 \(S\) 的数的个数，\(g(S)\) 为按位与之和包含 \(S\) 的选取方案数，则有
\[g(S)=2^{f(S)}-1 \]而 \(g(S)\) 其实就是容斥式子中 \(k\) 个集合的交的大小。也就是说
\[\sum_{|S|=k} g(S)=\sum_{a_i<a_{i+1}}\left|\bigcap_{i=1}^k\overline{S_{a_i}}\right| \]代入回容斥的式子当中
\[\left|\bigcap_{i=1}^m S_i\right|=|U|+\sum_{k=1}^m(-1)^k\sum_{|S|=k} g(S) \]问题就变成了求解 \(f(S)\)。而这就是一个超集和，用高维后缀和就可以解决。
时间复杂度 \(\mathcal{O}(m2^m)=\mathcal{O}(n\log n)\)。
P6442 [COCI2011-2012#6] KOŠARE
取出元素并集为全集，可以对元素取反，这样就转化为了取出元素交集为空。
那就跟上一道题完全一样了。
时间复杂度 \(\mathcal{O}(m2^m)\)。
CF383E Vowels
容斥，考虑求不包含任何一个元音字母的单词数。
枚举字符集 \(S\)，那么不合法的单词就会被包含在 \(\overline S\) 中。只需要求每个字符集包含的单词数。
做一遍高维前缀和就做完了。
令 \(\Sigma\) 为字符集大小，时间复杂度 \(\mathcal{O}(n+|\Sigma|2^{|\Sigma|})\)。
CF165E Compatible Numbers
\(a\operatorname{and}b=0\) 说明 \(b\in \overline a\)。做高维前缀和即可。输出满足要求的数只需要微调一下。
时间复杂度 \(\mathcal{O}(n\log n)\)。
标签：前缀,复杂度,容斥,mathcal,sum,高维 From： https://www.cnblogs.com/duckqwq/p/18132089