浅记高维前缀和

考虑如下问题：
记 \(y\subset x\leftrightarrow x\& y=y\)。若 \(x\subset y\)，称 \(x\) 为 \(y\) 的一个子集，\(y\) 为 \(x\) 的一个超集。
给定数组 \(f\)，求数组 \(g\)。其中 \(g_x=\sum_{y\subset x}{f_y}\)。
设 \(f\) 中最大的数二进制下共有 \(n\) 位。
如果直接枚举子集的话，时间复杂度为 \(O(3^n)\)，可以优化。
不妨考虑如下算法：

for(int i=0;i<n;i++){
    for(int j=0;j<1<<n;j++){
        if(!(j&1<<i)) f[j|1<<i]+=f[j];
    }
}

这个算法把 \(n\) 位的二进制数视作一个 \(n\) 维的每维为 \(0\) 或 \(1\) 的向量，整个过程是在对整个 \(n\) 维空间做前缀和。
具体一点，就是依次对于 \(0\sim n-1\) 维，把所有这一维是 \(0\) 的向量的前缀和累到 \(1\) 上。
正确性：
若 \(x\subset y\)，则在 \(x\) 和 \(y\) 最高的不同的一维会算到 \(x\)，在更低的位由于有高位不同不会算到。
若 \(x\not\subset y\)，因为所有能算到 \(x\) 的向量都是将 \(x\) 的某些维从0变成 1 得到的（相当于能算到 \(x\) 的都是 \(x\) 的超集），
而至少存在某一维 \(x\) 为1，\(y\)为0，所以 \(y\)不可能算到x。
时间复杂度\(O(2^nn)\)，空间复杂度\(O(2^n)\)。

例题：CF449D
给出 \(n\) 个数\(a_1,a_2,...,a_n\)，求有多少个非空子集，其中所有数与起来等于零。
设 \(f_x\) 表示 \(x\) 出现次数，用刚讲的高维前缀和方法算出 \(g_x=\sum_{y\subset x}{f_y}\)。
发现与起来为 \(x\) 的超集的子集个数很好算，即 \(2^{g_x}-1\)。
设与起来恰为 \(x\) 的子集个数为 \(h_x\)。令\(s_x=2^{g_x}-1\)，不难发现将 \(s\) 做高维前缀和的逆变换即得到 \(h\)，这个过程有点像容斥。

for(int i=0;i<n;i++){
    for(int j=0;j<1<<n;j++){
        if(j&1<<i) s[j^1<<i]-=s[j];
    }
}

答案即为 \(h_0\)。