-
给定 \(n, q\) 和 \(f(0), f(1), \dots, f(2^n - 1)\)。\(q\) 次询问，给定 \(S\)，求：
\[\sum_{S' \subseteq S} f(S') \] -
\(n \le 20\)，\(q \le 10^6\)。
令 \(S_i\) 表示 \(S\) 的第 \(i\) 个二进制位。
可以发现若 \(S' \subseteq S\)，那么对于所有 \(i\) 都有 \(S'_i \le S_i\)。也就是要求：
\[\sum_{S'_0 = 0}^{S_0}\sum_{S'_1 = 0}^{S_1} \sum_{S'_2 = 0}^{S_2}\dots, \sum_{S'_{n-1} = 0}^{S_{n-1}} f(S') \]发现这就是一个 \(n\) 维的前缀和的形式。
对于二维前缀和，除朴素的容斥做法 \(s_{i, j} = s_{i, j - 1} + s_{i - 1, j} - s_{i - 1, j - 1} + a_{i, j}\) 外，可以用这种方式：
for (int i = 1; i <= n; ++ i )
for (int j = 1; j <= n; ++ j )
a[i][j] += a[i][j - 1];
for (int i = 1; i <= n; ++ i )
for (int j = 1; j <= n; ++ j )
a[i][j] += a[i - 1][j];
第一个循环后，\(a_{i, j} = a_{i, 1} + a_{i, 2} + \dots + a_{i, j}\)，表示先对每行单独做一遍前缀和。
第二个循环后，\(a_{i, j}\) 就是真正的左上矩阵的和，此时是对每列单独做一遍前缀和。
同理可以延伸到三维：
for (int i = 1; i <= n; ++ i )
for (int j = 1; j <= n; ++ j )
for (int k = 1; k <= n; ++ k )
a[i][j][k] += a[i - 1][j][k];
for (int i = 1; i <= n; ++ i )
for (int j = 1; j <= n; ++ j )
for (int k = 1; k <= n; ++ k )
a[i][j][k] += a[i][j - 1][k];
for (int i = 1; i <= n; ++ i )
for (int j = 1; j <= n; ++ j )
for (int k = 1; k <= n; ++ k )
a[i][j][k] += a[i][j][k - 1];
枚举范围为 \([0, 1]\) 时就可以用位运算计算了。
我们令答案式为 \(g(S)\)。类比上边两份代码，可以得到：
for (int j = 0; j < n; ++ j )
for (int i = 0; i < (1 << n); ++ i )
if (i >> j & 1)
g[i] += g[i ^ (1 << j)];