SOS DP (sum over subsets): как за O(n·2^n) посчитать сумму по всем подмаскам каждой маски?
Дан массив a[mask] для всех масок . Нужно для каждой маски посчитать — сумму по всем её подмаскам. Наивно перебор подмасок даёт . Слышал про SOS DP за — как это работает?
2 ответа
SOS DP (Sum over Subsets) — это, по сути, -мерное префиксное суммирование по гиперкубу из 0/1 по каждому биту. Состояние dp[i][mask] = сумма по тем подмаскам mask, которые отличаются от mask только в первых i битах. После обработки всех n битов получаем сумму по всем подмаскам.
Компактная in-place версия:
int n;
vector<long long> f(1 << n); // изначально f = a
// f[mask] = a[mask];
for (int i = 0; i < n; ++i)
for (int mask = 0; mask < (1 << n); ++mask)
if (mask & (1 << i))
f[mask] += f[mask ^ (1 << i)]; // добавляем подмаску без бита i
// теперь f[mask] = sum_{sub ⊆ mask} a[sub]
Идея цикла по i: фиксируем бит i. Если он установлен в mask, к текущему f[mask] добавляем f маски без этого бита — так на каждом шаге «развязывается» один бит. Время , память . Для это — быстро.
Двойственный вариант — сумма по надмаскам (supersets): просто меняем условие на if (!(mask & (1<<i))) и f[mask] += f[mask | (1<<i)]. А обратное преобразование (Мёбиус по подмножествам, чтобы из сумм восстановить исходный a) — тот же цикл, но с -=:
for (int i = 0; i < n; ++i)
for (int mask = 0; mask < (1 << n); ++mask)
if (mask & (1 << i)) f[mask] -= f[mask ^ (1 << i)];
Это прямой и обратный «зета/мёбиус»-трансформ — фундамент для subset-sum свёрток (OR-свёртка). Порядок циклов важен: внешний по битам, внутренний по маскам, не наоборот.