高维前缀和(SOS dp)

A Xor B Problem again

二维前缀和

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        s[i][j] = s[i - 1][j] + s[i][j - 1] - s[i - 1][j - 1] + a[i][j];

其实也可以分开来写

for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= n; j++) {
        s[i][j] = s[i][j - 1] + a[i][j];
    }
}

for (int i = 1; i <= n; i++)
    for (int j = 1; j <= n; j++)
        s[i][j] += s[i - 1][j]; 

每一维分开求，这其实也是高维前缀和的求法。

高维前缀和

用一个二进制串来代表维数，例如1010，来表示一个四维的坐标系，那么sum[1010]统计的就是在四个维度都小于1010的数的和，即1010、1000、0010、0000。

代码如下

for (int i = 0; i <= 20; i++) // 枚举维度
    for (int j = (1 << MAX) - 1; j >= 0; j--) { // 枚举状态
        if (j >> i & 1) {
            sum[j] += sum[j ^ (1 << i)];
        }
    }