高维前缀和

$$
f_s=\sum_{t \subseteq s}a_t
$$

枚举二进制的每一维,然后依次求一遍前缀和

1
2
3
4
5
6
7
for(int i = 1 ; i <= n ; ++ i) {
for(int s = 0 ; s < U ; ++ s) {
if(s & (1 << (i - 1))) {
f[s] += f[s - (1 << (i - 1))];
}
}
}

1

$$
\begin{aligned}
\sum_{s \cap t=\emptyset} g_sg_t=\sum_{s}g_s\sum_{t \subseteq (U-s)}g_t
\end{aligned}
$$