高维前缀和

1原来我不会。

子集枚举

枚举一个集合的每个子集的所有子集。

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))];
    }
}

这该如何理解？

考虑一位一位地加入贡献。

或者说，每次枚举时都将高位的位置钦定好，只考虑低位位置子集所带来的贡献。

这么说太抽象了，举个例子吧。

假设当前枚举到了第 \(2\) 位，要贡献到 \(11111\) 。

那么我们就让当前的 \(11101\) 对它贡献。

此时，高位的三位是不变的，而 \(11101\) 已经是一个前三位不变，后两位是子集和的东西了。

即 \(11101\) 此时已经是 \(11100\) 与 \(11101\) 的和了。

那么就可以直接让它贡献到 \(11111\) 了。

当枚举到第三位时，我们钦定的就是高位的两位不变了。

对于 \(11111\) ，现在我们让 \(11011\) 贡献到它。

此时，\(11011\) 也是钦定了前两位，后两位的子集和了。

即 \(11011\) 此时是原来的 \(11000,11001,11010,11011\) 的和了。

那么也可以让它贡献到 \(11111\) 了。

类似的考虑问题即可。