SOS DP: сумма по подмаскам за O(n·2ⁿ) вместо O(3ⁿ)

SOS DP (sum over subsets) простыми словами: как посчитать сумму по всем подмаскам за O(n·2ⁿ), преобразования Зета и Мёбиуса, суммы по надмаскам, OR-свёртка и типичные задачи. Код на Python.

9 мин чтенияалгоритмы · динамическое программирование · битовые маски · python

Коротко

ПараметрЗначение
Задачадля каждой маски SS посчитать F[S]=∑T⊆Sa[T]F[S] = \sum_{T \subseteq S} a[T]
НаивноO(4n)O(4^n), перебор подмасок — O(3n)O(3^n)
SOS DPO(n⋅2n)O(n \cdot 2^n) времени, O(2n)O(2^n) памяти
Когда применятьn≤20–23n \le 20\text{–}23 бит, вопросы «по всем подмножествам / надмножествам»
Главная идеямногомерные префиксные суммы: по одной оси-биту за проход

SOS DP (Sum over Subsets) — это префиксные суммы на гиперкубе. Маска из nn бит — точка в nn-мерном кубе {0,1}n\{0,1\}^n, «подмаска» — точка, которая не больше по каждой координате. Значит, сумма по подмаскам — та же префиксная сумма, только в nn измерениях, и считается она так же: по одной оси за раз.

Постановка задачи

Дан массив a длины 2n2^n, индексы которого — маски. Нужно для каждой маски S найти сумму a[T] по всем T, являющимся подмасками S (то есть T & S == T).

Где это нужно на практике:

  • сколько чисел массива являются подмасками данного числа (a[T] — количество вхождений T);
  • для каждого x найти в массиве y с x & y == 0;
  • сколько подмножеств массива дают AND, равный нулю;
  • OR-свёртка двух массивов.

Все эти задачи разберём ниже. Сначала — как решать саму базовую задачу.

Наивное решение: O(4ⁿ)

В лоб: для каждой маски перебрать все 2n2^n кандидатов и проверить, подмаска ли это.

def naive(a, n): F = [0] * (1 << n) for mask in range(1 << n): for sub in range(1 << n): if sub & mask == sub: F[mask] += a[sub] return F

2n⋅2n=4n2^n \cdot 2^n = 4^n операций. При n=20n = 20 это 101210^{12} — не дождаться.

Перебор подмасок: O(3ⁿ)

Подмаски можно перебирать без проверки, идиомой sub = (sub - 1) & mask. Подробно она разобрана в статье про ДП по битовым маскам, а вывод нам нужен такой: перебор идёт только по реальным подмаскам.

def submasks(a, n): F = [0] * (1 << n) for mask in range(1 << n): sub = mask while True: F[mask] += a[sub] if sub == 0: break sub = (sub - 1) & mask return F

Почему 3n3^n? Сумма по всем маскам числа их подмасок — это количество пар (T⊆S)(T \subseteq S). Каждый бит в такой паре находится в одном из трёх состояний: нет ни в SS, ни в TT; есть в SS, но не в TT; есть в обоих. Итого 3n3^n пар.

Это уже намного лучше, но 320≈3.5⋅1093^{20} \approx 3.5 \cdot 10^9 — для n=20n = 20 всё ещё слишком медленно. Хватает примерно до n=15–16n = 15\text{–}16.

Главная неэффективность: суммы для 1110 и 1101 обе заново складывают вклад 1100, 0100 и так далее. Одни и те же частичные суммы пересчитываются много раз.

Идея SOS DP

Вспомним двумерные префиксные суммы. Сумму по прямоугольнику [0..x]×[0..y][0..x] \times [0..y] можно считать через формулу включений-исключений, а можно проще: сначала префиксные суммы по каждой строке, потом по каждому столбцу. Два независимых прохода — и готово.

Маска из nn бит — точка с nn координатами, каждая равна 0 или 1. Условие «TT — подмаска SS» означает Ti≤SiT_i \le S_i по каждой координате. То есть F[S]F[S] — это nn-мерная префиксная сумма. Делаем nn проходов, по одному на бит:

  • проход по биту ii: для каждой маски, где бит ii стоит, прибавляем значение маски с выключенным битом ii.

После прохода по биту ii значение F[mask] равно сумме a[T] по всем T, которые совпадают с mask в старших битах (от i+1i+1 и выше) и являются подмаской mask в битах 0..i0..i. После последнего прохода ограничение «совпадают» исчезает — получаем сумму по всем подмаскам.

def sos(a, n): F = a[:] for i in range(n): bit = 1 << i for mask in range(1 << n): if mask & bit: F[mask] += F[mask ^ bit] return F

Восемь строк, n⋅2nn \cdot 2^n операций. Для n=20n = 20 это около 21 миллиона — на C++ доли секунды.

Почему каждая подмаска учитывается ровно один раз

Возьмём подмаску TT маски SS. Путь от TT к SS в процессе вычислений один: на проходе по биту ii мы «включаем» этот бит, если он есть в SS и отсутствует в TT, и ничего не делаем, если биты совпадают. Порядок проходов фиксирован, поэтому и путь единственный. Нет повторного счёта — нет и пересечений, которые пришлось бы вычитать.

Важен ли порядок внутреннего цикла

Нет. На проходе по биту ii мы читаем F[mask ^ bit] — маску с выключенным битом ii. Её значение в этом проходе не меняется (меняются только маски с включённым битом). Поэтому обход масок можно делать в любом порядке, а вот внешний цикл обязательно по битам.

Разбор на примере

n=3n = 3, a = [3, 1, 4, 1, 5, 9, 2, 6] (индекс — маска от 000 до 111).

Маска000001010011100101110111
a31415926
бит 0344551428
бит 13479514722
бит 234798181431

Проверим F[101]: подмаски 000, 001, 100, 101, сумма 3+1+5+9=183 + 1 + 5 + 9 = 18. Совпадает. F[111] — сумма всего массива, 3131.

На каждом проходе обновляется ровно половина ячеек: те, где соответствующий бит равен единице.

Насколько это быстрее на практике

На Python при n=16n = 16 перебор подмасок занимает около 5–6 секунд, а SOS DP — меньше 0.1 секунды. Разница в (3/2)16/16≈40(3/2)^{16} / 16 \approx 40 раз по числу операций, на практике ещё больше: у SOS простой линейный цикл без ветвлений по while.

nn3n3^nn⋅2nn \cdot 2^n
1059 04910 240
1643 046 7211 048 576
203 486 784 40120 971 520

Та же функция на JavaScript, если удобнее:

function sos(a, n) { const F = Int32Array.from(a) for (let i = 0; i < n; i++) { const bit = 1 << i for (let mask = 0; mask < 1 << n; mask++) { if (mask & bit) F[mask] += F[mask ^ bit] } } return F }

Преобразования Зета и Мёбиуса

То, что мы посчитали, в литературе называется преобразованием Зета (zeta transform) на решётке подмножеств:

F[S]=∑T⊆Sa[T]F[S] = \sum_{T \subseteq S} a[T]

У него есть обратное — преобразование Мёбиуса: по готовым FF восстановить исходные aa. Формула через включения-исключения:

a[S]=∑T⊆S(−1)∣S∣−∣T∣F[T]a[S] = \sum_{T \subseteq S} (-1)^{|S| - |T|} F[T]

Считать по формуле напрямую — опять 3n3^n. Но обращать префиксные суммы можно тем же трюком, что и в одномерном случае: вместо «прибавить соседа» — «вычесть соседа». Каждый проход по биту обратим сам по себе, значит, и вся композиция обратима.

def mobius(F, n): a = F[:] for i in range(n): bit = 1 << i for mask in range(1 << n): if mask & bit: a[mask] -= a[mask ^ bit] return a

mobius(sos(a, n), n) == a для любого a — можно проверить на случайных массивах. Порядок битов в Мёбиусе тоже не важен: проходы по разным битам коммутируют.

Когда это нужно? Типичный сценарий: легко посчитать F[S]F[S] — «сколько объектов удовлетворяют условию не больше SS», а спрашивают a[S]a[S] — «сколько ровно SS». Мёбиус переводит одно в другое. Это та же формула включений-исключений из комбинаторики, только посчитанная для всех масок сразу за O(n⋅2n)O(n \cdot 2^n).

Суммы по надмаскам

Часто нужно обратное направление: G[S]=∑T⊇Sa[T]G[S] = \sum_{T \supseteq S} a[T] — сумма по всем масках, содержащим SS. Меняется одна строчка: теперь маска с выключенным битом забирает значение у маски с включённым.

def sos_supersets(a, n): G = a[:] for i in range(n): bit = 1 << i for mask in range(1 << n): if not mask & bit: G[mask] += G[mask | bit] return G

Альтернатива — проинвертировать маски (a'[S] = a[~S]) и применить обычный SOS. Но отдельная функция понятнее и не ловит ошибок с дополнением до nn бит.

Типичные задачи

1. Для каждого x найти y с x & y == 0

Дан массив чисел до 2222^{22}. Для каждого x нужно вывести любой y из массива, у которого x & y == 0, или -1. Это известная задача Codeforces «Compatible Numbers».

x & y == 0 означает: y — подмаска дополнения ~x. Значит, нужно для каждой маски знать «какую-нибудь подмаску, которая есть в массиве». Это SOS, где вместо суммы — операция «взять любой найденный элемент».

def compatible(nums): n = max(nums).bit_length() or 1 full = (1 << n) - 1 best = [-1] * (1 << n) for x in nums: best[x] = x for i in range(n): bit = 1 << i for mask in range(1 << n): if mask & bit and best[mask] == -1: best[mask] = best[mask ^ bit] return [best[full ^ x] for x in nums] print(compatible([90, 36])) # [36, 90] print(compatible([10, 6, 9, 8, 2])) # [-1, 9, 6, 6, 9]

Вывод: SOS работает не только с суммой. Подходит любая ассоциативная и коммутативная операция, которой не страшно учесть элемент один раз: сумма, максимум, минимум, OR, «любой непустой». Для максимума и минимума не страшен даже повторный учёт.

2. Количество подмножеств с AND = 0

Дан массив из mm чисел до 2202^{20}. Сколько непустых подмножеств имеют побитовый AND, равный нулю? (Codeforces «Jzzhu and Numbers».)

Посчитать «AND ровно 0» трудно, а «AND содержит маску SS» — легко. AND подмножества содержит SS тогда и только тогда, когда каждый элемент содержит SS. Если таких элементов c[S]c[S], то подходящих непустых подмножеств 2c[S]−12^{c[S]} - 1. А c[S]c[S] — это как раз сумма по надмаскам от массива частот.

Дальше включения-исключения: подмножества с AND = 0 — это все подмножества минус те, у которых в AND есть хотя бы один бит.

ans=∑S(−1)∣S∣(2c[S]−1)\text{ans} = \sum_{S} (-1)^{|S|} \left(2^{c[S]} - 1\right)
MOD = 10**9 + 7 def count_and_zero(nums): n = max(nums).bit_length() or 1 cnt = [0] * (1 << n) for x in nums: cnt[x] += 1 for i in range(n): # суммы по надмаскам bit = 1 << i for mask in range(1 << n): if not mask & bit: cnt[mask] += cnt[mask | bit] ans = 0 for mask in range(1 << n): sign = -1 if bin(mask).count('1') % 2 else 1 ans += sign * (pow(2, cnt[mask], MOD) - 1) return ans % MOD print(count_and_zero([2, 3, 3])) # 0 print(count_and_zero([0, 1, 2, 3])) # 10

Последний цикл — это по сути Мёбиус по надмаскам, взятый только в точке S=0S = 0. Если бы спрашивали «сколько подмножеств с AND, равным ровно SS, для каждого SS», мы применили бы полное обратное преобразование.

3. OR-свёртка

Даны массивы f и g длины 2n2^n. Нужно посчитать

h[S]=∑i∣j=Sf[i]⋅g[j]h[S] = \sum_{i \mid j = S} f[i] \cdot g[j]

Наивно — 4n4^n. Ключевое наблюдение: i∣j⊆Si \mid j \subseteq S тогда и только тогда, когда i⊆Si \subseteq S и j⊆Sj \subseteq S. Значит, после Зета-преобразования свёртка превращается в поэлементное произведение:

h^[S]=f^[S]⋅g^[S]\hat{h}[S] = \hat{f}[S] \cdot \hat{g}[S]

Остаётся вернуться назад Мёбиусом:

def or_convolution(f, g, n): F, G = sos(f, n), sos(g, n) H = [x * y for x, y in zip(F, G)] return mobius(H, n)

Итог — O(n⋅2n)O(n \cdot 2^n). AND-свёртка делается так же, только через суммы по надмаскам. Это прямой аналог БПФ для полиномов: перейти в «удобный базис», перемножить поточечно, вернуться. Для XOR-свёртки нужен уже другой базис — преобразование Уолша–Адамара, но устроено оно похоже: тоже nn проходов по битам.

4. Подсчёт пар с условием на биты

«Сколько пар (i,j)(i, j) таких, что ai & aj=aia_i \,\&\, a_j = a_i» (то есть aia_i — подмаска aja_j)? Строим частоты, считаем SOS, затем для каждого aja_j берём F[aj]F[a_j] и вычитаем случаи i=ji = j. Вся задача — O(n⋅2n+m)O(n \cdot 2^n + m) вместо O(m2)O(m^2).

Тот же шаблон работает для «сколько чисел массива являются надмаской xx» — запросы отвечаются за O(1)O(1) после предподсчёта.

5. Не сумма, а два максимума

Задача с AtCoder (ARC 100, «Or Plus Max»): дан массив a длины 2n2^n. Для каждого KK от 1 до 2n−12^n - 1 найти максимум ai+aja_i + a_j по парам i<ji < j с (i∣j)≤K(i \mid j) \le K.

Условие (i∣j)≤K(i \mid j) \le K неудобное, поэтому решаем более простую задачу: максимум по парам с (i∣j)⊆k(i \mid j) \subseteq k — то есть обе позиции подмаски kk. Ответ для KK — максимум таких значений по всем k≤Kk \le K, это обычный префиксный максимум. Ведь если i∣j≤Ki \mid j \le K, то пара учтётся при k=i∣jk = i \mid j.

Для каждой маски храним индексы двух лучших элементов среди её подмасок. Объединение двух таких списков — снова два лучших, операция ассоциативна. Хранить индексы, а не значения, важно: иначе один и тот же элемент может прийти из двух ветвей и посчитаться дважды.

def or_plus_max(a, n): # top[mask] — индексы двух максимальных элементов среди подмасок mask top = [[m] for m in range(1 << n)] for i in range(n): bit = 1 << i for mask in range(1 << n): if mask & bit: merged = set(top[mask]) | set(top[mask ^ bit]) top[mask] = sorted(merged, key=lambda j: -a[j])[:2] res, best = [], float('-inf') for k in range(1, 1 << n): x, y = top[k] best = max(best, a[x] + a[y]) res.append(best) return res print(or_plus_max([1, 2, 3, 1], 2)) # [3, 4, 5]

У каждой ненулевой маски не меньше двух подмасок, поэтому в top[k] при k≥1k \ge 1 всегда два индекса. Приём «хранить top-2 вместо суммы» встречается часто: так ищут, например, максимальное ai & aja_i \,\&\, a_j или лучшую пару с ограничением на биты.

Сложность и ограничения

  • Время: O(n⋅2n)O(n \cdot 2^n). Для n=20n = 20 — около 2⋅1072 \cdot 10^7, для n=23n = 23 — около 2⋅1082 \cdot 10^8 (на C++ ещё нормально).
  • Память: O(2n)O(2^n), массив обновляется на месте. При n=22n = 22 и int64 это 32 МБ. Если значения маленькие, используйте int32.
  • Python: чистый цикл тянет n≤16–18n \le 16\text{–}18. Для большего нужен NumPy.

Векторизация на NumPy

Проход по биту ii можно сделать одной операцией. Если посмотреть на массив длины 2n2^n как на трёхмерный формы (2n−i−1,2,2i)(2^{n-i-1}, 2, 2^i), то средняя ось — это как раз значение бита ii. Остаётся прибавить срез «бит выключен» к срезу «бит включён»:

import numpy as np def sos_numpy(a, n): F = np.array(a, dtype=np.int64) for i in range(n): v = F.reshape(-1, 2, 1 << i) # ось 1 — значение бита i v[:, 1, :] += v[:, 0, :] return F

reshape возвращает представление, а не копию, поэтому изменения попадают в исходный F. Такая версия при n=22n = 22 работает за доли секунды — Python перестаёт быть ограничением. Для надмасок меняются местами индексы: v[:, 0, :] += v[:, 1, :], для Мёбиуса — -= вместо +=.

Типичные ошибки

  1. Перепутать порядок циклов. Внешний цикл — по битам, внутренний — по маскам. Если сделать наоборот (для каждой маски перебрать биты), получится неправильный результат: часть подмасок посчитается несколько раз, часть не посчитается вовсе.
  2. Не скопировать массив. F = a вместо F = a[:] испортит входные данные — обидно, если a нужен дальше (например, для свёртки).
  3. Неверная разрядность. Если числа до 10610^6, нужно n=20n = 20 бит, а не «сколько элементов в массиве». Дополнение ~x в Python отрицательное — используйте full ^ x, где full = (1 << n) - 1.
  4. Переполнение. Суммы по подмаскам растут быстро: F[full]F[\text{full}] — сумма всего массива. В C++ берите long long или работайте по модулю.
  5. Мёбиус с прибавлением. Обратное преобразование — это вычитание. Если «обращать» тем же sos, получится двойное Зета, а не исходный массив.
  6. Путать подмаски и надмаски. Перед кодом сформулируйте: нужен T⊆ST \subseteq S или T⊇ST \supseteq S. В задачах про AND обычно надмаски, про OR — подмаски.

Где встречается на собеседованиях

Честно: на обычном собеседовании в продуктовую компанию SOS DP почти не спрашивают. Это олимпиадная техника, она чаще встречается на Codeforces (Div. 1–2, задачи уровня D–E) и на AtCoder. Если на интервью дают задачу с битовыми масками, обычно хватает базовых битовых операций или перебора подмножеств.

Но знать SOS полезно по двум причинам. Во-первых, на собеседованиях в компании с сильным алгоритмическим фильтром и на олимпиадных отборах встречаются задачи «для каждого числа найти совместимое», где O(m2)O(m^2) не проходит. Во-вторых, это хороший пример переиспользования идеи: если вы поняли, что сумма по подмаскам — это многомерная префиксная сумма, вы сможете объяснить решение интервьюеру за минуту, а не воспроизводить заученный код.

Признаки, что задача — на SOS:

  • значения до 2202^{20} или около того, а элементов много (до 10610^6);
  • в условии AND, OR или «является подмножеством»;
  • нужно ответить «для каждого x» или посчитать что-то по всем маскам сразу;
  • решение через перебор подмасок даёт 3n3^n, и это на грани.

Итог

  • SOS DP — nn-мерная префиксная сумма на гиперкубе масок, O(n⋅2n)O(n \cdot 2^n) вместо O(3n)O(3^n).
  • Внешний цикл по битам, внутренний по маскам, одна строка обновления.
  • Мёбиус — то же самое с вычитанием, он обращает Зета.
  • Надмаски — зеркальная версия, нужна для задач про AND.
  • Вместе Зета и Мёбиус дают OR- и AND-свёртку за O(n⋅2n)O(n \cdot 2^n).

Если ещё не знакомы с базой, начните с ДП по битовым маскам — там разобраны кодирование подмножеств и перебор подмасок, на которых строится эта статья.

Потренироваться в спокойной обстановке

Все задачи