今天集训的题我已经写不动了，下周开始会复习 dp, 现在就提前把一些东西补一补，这个说不好会在之后状压里边用到。
枚举子集
如何遍历一个集合的子集
通常我们会采取递归的方式，是 \(O(2^n)\) 的，但是这个样子我们在具体使用的时候是很不方便的，尤其是我们在对于一些二进制的东西做文章的时候。
所以我们需要这个循环形式的枚举子集。
for(int s=u; s; s=(s-1)&u)
这个样子我们就是在枚举 \(s\) 为 \(u\) 的子集了。
先谈正确性，后谈复杂度。
为什么这个东西可以不重不漏？
很明显的，我们的减一是严格下降的，按位与是严格不升的，每一次操作必然会变小，故不会重复。
至于正确性，我们的减一实际上是删除 s 中最后一个一，再把它的右边全部变成一。我们为了让这个东西变成新的子集，我们需要删除 u 之中没有包含的 1,这个我们直接按位与清除一下就好啦。
时间复杂度就是明显的了，我们仅仅需要关注 1 的数量，复杂度自然是 \(O(2^{popcount(u)})\)。
如何遍历一个集合子集的子集
for(int m=0; m<(1<<n); ++m){for(int s=m; s; s=(s-1)&m){......}
}
也就是直接套用上边的。
这个东西的复杂度是奇妙的，它竟然是 \(O(3^n)\) 的，比我们想象中要底很多很多。
如果 \(m\) 拥有 \(k\) 个 \(1\)，那么我们会枚举出来 \(2^k\) 个子集。
而对于一个 \(k\)，我们可以找出来 \(\binom{n}{k}\) 个对应的集合满足有 \(k\) 个 1。
总数就变成了：\(\sum_{k=0}^{n}\binom{n}{k}2^k\)。
根据二项式定理，这个东西等于 \((1+2)^n\) 的展开，因此是 \(O(3^n)\) 的，似乎很有用，避免了我们傻傻的 \(2^n\times 2^n\) 的枚举。
高维前缀和
又称 sosdp，我不知道为什么。
我们平常做一维或者二维前缀和都是用容斥原理求的，以二维为例。
\(sum[i][j]=sum[i-1][j]+sum[i][j-1]-sum[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];
like that.
这个样子是一样的，我们采取这个思路。
对于求解 \(0\le i\le 2^n-1\)，\(\sum_{j\in i} a[j]\) 这样的东西，我们可以使用这个思路。
我们不妨把集合看作多维空间中的点，第 \(i\) 位的 0/1 表示第 \(i\) 维的坐标。
于是乎就可以像之前那么做了，枚举维数与子集，在当前维度是 1 的地方从当前维度是 0 的地方转移过来。
for(int i=0; i<n; ++i){for(int j=0; j<(1<<n); ++j){if(j&(1<<i)) dp[j]+=dp[j^(1<<i)];}
}
于是就没有了，显然我们从枚举子集的 \(O(3^n)\) 优化到了 \(O(n\times 2^n)\)。