高维前缀和
原来我不会。
看不懂只能自己编了。
子集枚举
枚举一个集合的每个子集的所有子集。
for(int s=0;s<(1<<n);s++){
for(int s0=s;;s0=s0&(s0-1)){
cout<<s0<<' ';
}
}
其中 \(s0\) 即为枚举的每个子集的所有子集。
这是为什么？
第一层循环中，我们枚举了一个子集。
那么第二层循环中，我们就要枚举这个子集的所有子集。
从 \(s\) 本身开始，从大往小降序枚举。
我们想快速从一个子集跳转到比它小的第一个子集。
分类讨论一下：
若当前的子集最低位为 \(1\)，比它小的第一个子集显然是它 \(-1\)。
否则，当前子集最低位为 \(0\)，考虑 \(-1\) 以后会发生什么变化。
发现，会将第一段后缀 \(10000000……\) 变成 \(011111111……\),也就是让最低位的 \(1\) 变成了 \(0\)，最低位之前的 \(0\) 都变成了 \(1\)。
此时只需保留原集合中的所有位置即可，所以 \(\&s\) 就行了。
发现我们的枚举不重不漏，那么复杂度就是所有子集的子集个数的和。
即 \(\sum_{i=0}^{n}C_{n}^{i}2^i=3^n\)。
高维前缀和
对于原集合的每一个子集，都有一个初始权值，现在求每一个子集的子集权值和。
for(int i=1;i<=n;i++){
for(int j=0;j<(1<<n);j++){
if(s&(1<<(i-1))) f[s]+=f[s^(1<<(i-1))];
}
}
这该如何理解？
考虑一位一位地加入贡献。
或者说，每次枚举时都将高位的位置钦定不变，某一个 \(1\) 位钦定为 \(0\)，只考虑低位位置子集所带来的贡献。
这么说太抽象了，举个例子吧。
假设当前枚举到了第 \(2\) 位，要贡献到 \(11111\) 。
那么我们就让当前的 \(11101\) 对它贡献。
此时，高位的三位是不变的，而 \(11101\) 已经是一个前三位不变，后两位是子集和的东西了。
即 \(11101\) 此时已经是 \(11100\) 与 \(11101\) 的和了。
那么就可以直接让它贡献到 \(11111\) 了。
当枚举到第三位时，我们钦定的就是高位的两位不变了。
对于 \(11111\) ，现在我们让 \(11011\) 贡献到它。
此时，\(11011\) 也是钦定了前两位，后两位的子集和了。
即 \(11011\) 此时是原来的 \(11000,11001,11010,11011\) 的和了。
那么也可以让它贡献到 \(11111\) 了。
类似的考虑问题即可。
由于每次钦定的 \(0\) 的位置不同，所以不重不漏。
超集是同理的，每次钦定高位不变，当前 \(0\) 位为 \(1\)，考虑低位的超集带来的贡献即可。
for(int i=1;i<=n;i++){
for(int j=0;j<(1<<n);j++){
if(j&(1<<(i-1))) f[s^(1<<(i-1))]+=f[s];
}
}