如何优雅的处理特殊的子集 dp 问题

标签：... 前缀 sum 优雅 leq 子集 高维 dp

sosdp & 高维前缀和

求

\[g_i = \sum_{j \& i > 0} f_j (i \leq 2^n - 1) \]

我们将 \(i, j\) 进行二进制拆分，拆成 \(n\) 个维度。

类似于：

\[g_{a_1, a_2, a_3, a_4, a_5 ... a_n} = \sum_{a_k \leq b_k} f_{b_1, b_2, b_3, b_4, b_5 ... b_n} (a_i, b_i \subseteq \{0, 1\}) \]

我们发现这个问题本质上就转化成了一个高维前缀和。

code :

int len = (1 << n) - 1;
rep(i, 0, n - 1) {
    rep(j, 0, len) {
        if(!(j & (1 << i))) f[j | (1 << i)] = (f[j | (1 << i)] + f[j]) % P;
    }
}

例题：
CF1679E Typical Party in Dorm

标签：...,前缀,sum,优雅,leq,子集,高维,dp
From： https://www.cnblogs.com/Kafuchino/p/18003741