高维前缀和

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

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

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}
$$