最近做的题里面有这个东西，于是写一篇博客总结一下吧。
枚举子集
枚举子集就是状压的时候枚举其中的二进制位中的1的子集。直接暴力枚举二进制位时间复杂度是(O(4^n))，但是我们可以发现，对于每一位有以下三种状态，在枚举的子集中为1，在子集中为0且在原状态中为1，以及在原状态中为0。这样，对于1到(2^n)的数中，子集的总数为(3^n)，这样，通过一些比较优秀的枚举，时间复杂度即为(O(3^n))。代码如下：
for(int i=s;;i=(i-1)&s) {
//do sth...
if(!i) break;
}
其中，对于每次循环的i，枚举的即是s的子集。
枚举补集的道理和枚举子集是一样的，因为枚举补集就相当于枚举0的子集。
例题：[noip 2017] 宝藏。
高维前缀和
高维前缀和就是说把原来的数组变为其下标的子集的元素之和，高维差分就是把这个反着干，暴力的复杂度就是(O(3^n))。
还有一种方法可以在(O(n*2^n))中完成高维前缀和，代码如下：
for(int i=1;i<s;i<<=1)
for(int j=0;j<s;j++)
if(i&j) f[j]+=f[i^j];
高维差分大概就是把枚举顺序改改就差不多了。
例题：
HDU5765
题意大概就是给定n个点m条边的无向图，求出其中每条边在图的(最小)割上出现了几次，n<=20。图的割为一个边的集合，断开这些边后图不连通。图的(最小)割定义为不存在其他的割为他的子集。
很显然，可以用状态压缩枚举一个联通块来表示一个割，该位为1表示在联通块内。如果一个状态及其补集均为联通块，则该联通块对应了一个割。
对于所有的割做一个高维前缀和，对于每一条边，其两端点所对应的状态即为该边不在任何一个割内的答案。
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int Maxn=2100000;
int t,n,m,l[Maxn],r[Maxn],g[Maxn],f[Maxn],dp[Maxn];
int main() {
scanf("%d",&t);
for(int o=1;o<=t;o++) {
printf("Case #%d:",o);
scanf("%d%d",&n,&m);
int end=(1<<n)-1,ans=0;
memset(g,0,sizeof(g));
for(int i=1;i<=m;i++) {
scanf("%d%d",&l[i],&r[i]);
g[l[i]]|=1<<r[i];
g[r[i]]|=1<<l[i];
}
dp[0]=1;
for(int i=1;i<=end;i++)
if((i&(-i))!=i)
for(int j=0,temp=1;j<n;j++,temp<<=1)
if(i&temp&&(dp[i]=dp[i^temp]&&(i&g[j])))
break;
else;
else dp[i]=1;
dp[0]=0,dp[end]=0;
for(int i=1;i<=end;i++)
f[i]=dp[i]&dp[(~i)&end],ans+=f[i];
ans/=2;
for(int i=0,temp=1;i<n;i++,temp<<=1)
for(int j=1;j<=end;j++)
if((j&temp)==0) f[j]+=f[j^temp];
for(int i=1;i<=m;i++) printf(" %d",ans-f[(1<<l[i])|(1<<r[i])]);
puts("");
}
return 0;
}