SOS DP: сумма по подмаскам за O(n·2ⁿ) вместо O(3ⁿ)
SOS DP (sum over subsets) простыми словами: как посчитать сумму по всем подмаскам за O(n·2ⁿ), преобразования Зета и Мёбиуса, суммы по надмаскам, OR-свёртка и типичные задачи. Код на Python.
Коротко
| Параметр | Значение |
|---|---|
| Задача | для каждой маски посчитать |
| Наивно | , перебор подмасок — |
| SOS DP | времени, памяти |
| Когда применять | бит, вопросы «по всем подмножествам / надмножествам» |
| Главная идея | многомерные префиксные суммы: по одной оси-биту за проход |
SOS DP (Sum over Subsets) — это префиксные суммы на гиперкубе. Маска из бит — точка в -мерном кубе , «подмаска» — точка, которая не больше по каждой координате. Значит, сумма по подмаскам — та же префиксная сумма, только в измерениях, и считается она так же: по одной оси за раз.
Постановка задачи
Дан массив a длины , индексы которого — маски. Нужно для каждой маски S найти сумму a[T] по всем T, являющимся подмасками S (то есть T & S == T).
Где это нужно на практике:
- сколько чисел массива являются подмасками данного числа (
a[T]— количество вхожденийT); - для каждого
xнайти в массивеyсx & y == 0; - сколько подмножеств массива дают AND, равный нулю;
- OR-свёртка двух массивов.
Все эти задачи разберём ниже. Сначала — как решать саму базовую задачу.
Наивное решение: O(4ⁿ)
В лоб: для каждой маски перебрать все кандидатов и проверить, подмаска ли это.
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
операций. При это — не дождаться.
Перебор подмасок: 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
Почему ? Сумма по всем маскам числа их подмасок — это количество пар . Каждый бит в такой паре находится в одном из трёх состояний: нет ни в , ни в ; есть в , но не в ; есть в обоих. Итого пар.
Это уже намного лучше, но — для всё ещё слишком медленно. Хватает примерно до .
Главная неэффективность: суммы для 1110 и 1101 обе заново складывают вклад 1100, 0100 и так далее. Одни и те же частичные суммы пересчитываются много раз.
Идея SOS DP
Вспомним двумерные префиксные суммы. Сумму по прямоугольнику можно считать через формулу включений-исключений, а можно проще: сначала префиксные суммы по каждой строке, потом по каждому столбцу. Два независимых прохода — и готово.
Маска из бит — точка с координатами, каждая равна 0 или 1. Условие « — подмаска » означает по каждой координате. То есть — это -мерная префиксная сумма. Делаем проходов, по одному на бит:
- проход по биту : для каждой маски, где бит стоит, прибавляем значение маски с выключенным битом .
После прохода по биту значение F[mask] равно сумме a[T] по всем T, которые совпадают с mask в старших битах (от и выше) и являются подмаской mask в битах . После последнего прохода ограничение «совпадают» исчезает — получаем сумму по всем подмаскам.
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
Восемь строк, операций. Для это около 21 миллиона — на C++ доли секунды.
Почему каждая подмаска учитывается ровно один раз
Возьмём подмаску маски . Путь от к в процессе вычислений один: на проходе по биту мы «включаем» этот бит, если он есть в и отсутствует в , и ничего не делаем, если биты совпадают. Порядок проходов фиксирован, поэтому и путь единственный. Нет повторного счёта — нет и пересечений, которые пришлось бы вычитать.
Важен ли порядок внутреннего цикла
Нет. На проходе по биту мы читаем F[mask ^ bit] — маску с выключенным битом . Её значение в этом проходе не меняется (меняются только маски с включённым битом). Поэтому обход масок можно делать в любом порядке, а вот внешний цикл обязательно по битам.
Разбор на примере
, a = [3, 1, 4, 1, 5, 9, 2, 6] (индекс — маска от 000 до 111).
| Маска | 000 | 001 | 010 | 011 | 100 | 101 | 110 | 111 |
|---|---|---|---|---|---|---|---|---|
a | 3 | 1 | 4 | 1 | 5 | 9 | 2 | 6 |
| бит 0 | 3 | 4 | 4 | 5 | 5 | 14 | 2 | 8 |
| бит 1 | 3 | 4 | 7 | 9 | 5 | 14 | 7 | 22 |
| бит 2 | 3 | 4 | 7 | 9 | 8 | 18 | 14 | 31 |
Проверим F[101]: подмаски 000, 001, 100, 101, сумма . Совпадает. F[111] — сумма всего массива, .
На каждом проходе обновляется ровно половина ячеек: те, где соответствующий бит равен единице.
Насколько это быстрее на практике
На Python при перебор подмасок занимает около 5–6 секунд, а SOS DP — меньше 0.1 секунды. Разница в раз по числу операций, на практике ещё больше: у SOS простой линейный цикл без ветвлений по while.
| 10 | 59 049 | 10 240 |
| 16 | 43 046 721 | 1 048 576 |
| 20 | 3 486 784 401 | 20 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) на решётке подмножеств:
У него есть обратное — преобразование Мёбиуса: по готовым восстановить исходные . Формула через включения-исключения:
Считать по формуле напрямую — опять . Но обращать префиксные суммы можно тем же трюком, что и в одномерном случае: вместо «прибавить соседа» — «вычесть соседа». Каждый проход по биту обратим сам по себе, значит, и вся композиция обратима.
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 — можно проверить на случайных массивах. Порядок битов в Мёбиусе тоже не важен: проходы по разным битам коммутируют.
Когда это нужно? Типичный сценарий: легко посчитать — «сколько объектов удовлетворяют условию не больше », а спрашивают — «сколько ровно ». Мёбиус переводит одно в другое. Это та же формула включений-исключений из комбинаторики, только посчитанная для всех масок сразу за .
Суммы по надмаскам
Часто нужно обратное направление: — сумма по всем масках, содержащим . Меняется одна строчка: теперь маска с выключенным битом забирает значение у маски с включённым.
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. Но отдельная функция понятнее и не ловит ошибок с дополнением до бит.
Типичные задачи
1. Для каждого x найти y с x & y == 0
Дан массив чисел до . Для каждого 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
Дан массив из чисел до . Сколько непустых подмножеств имеют побитовый AND, равный нулю? (Codeforces «Jzzhu and Numbers».)
Посчитать «AND ровно 0» трудно, а «AND содержит маску » — легко. AND подмножества содержит тогда и только тогда, когда каждый элемент содержит . Если таких элементов , то подходящих непустых подмножеств . А — это как раз сумма по надмаскам от массива частот.
Дальше включения-исключения: подмножества с AND = 0 — это все подмножества минус те, у которых в AND есть хотя бы один бит.
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
Последний цикл — это по сути Мёбиус по надмаскам, взятый только в точке . Если бы спрашивали «сколько подмножеств с AND, равным ровно , для каждого », мы применили бы полное обратное преобразование.
3. OR-свёртка
Даны массивы f и g длины . Нужно посчитать
Наивно — . Ключевое наблюдение: тогда и только тогда, когда и . Значит, после Зета-преобразования свёртка превращается в поэлементное произведение:
Остаётся вернуться назад Мёбиусом:
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)
Итог — . AND-свёртка делается так же, только через суммы по надмаскам. Это прямой аналог БПФ для полиномов: перейти в «удобный базис», перемножить поточечно, вернуться. Для XOR-свёртки нужен уже другой базис — преобразование Уолша–Адамара, но устроено оно похоже: тоже проходов по битам.
4. Подсчёт пар с условием на биты
«Сколько пар таких, что » (то есть — подмаска )? Строим частоты, считаем SOS, затем для каждого берём и вычитаем случаи . Вся задача — вместо .
Тот же шаблон работает для «сколько чисел массива являются надмаской » — запросы отвечаются за после предподсчёта.
5. Не сумма, а два максимума
Задача с AtCoder (ARC 100, «Or Plus Max»): дан массив a длины . Для каждого от 1 до найти максимум по парам с .
Условие неудобное, поэтому решаем более простую задачу: максимум по парам с — то есть обе позиции подмаски . Ответ для — максимум таких значений по всем , это обычный префиксный максимум. Ведь если , то пара учтётся при .
Для каждой маски храним индексы двух лучших элементов среди её подмасок. Объединение двух таких списков — снова два лучших, операция ассоциативна. Хранить индексы, а не значения, важно: иначе один и тот же элемент может прийти из двух ветвей и посчитаться дважды.
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] при всегда два индекса. Приём «хранить top-2 вместо суммы» встречается часто: так ищут, например, максимальное или лучшую пару с ограничением на биты.
Сложность и ограничения
- Время: . Для — около , для — около (на C++ ещё нормально).
- Память: , массив обновляется на месте. При и
int64это 32 МБ. Если значения маленькие, используйтеint32. - Python: чистый цикл тянет . Для большего нужен NumPy.
Векторизация на NumPy
Проход по биту можно сделать одной операцией. Если посмотреть на массив длины как на трёхмерный формы , то средняя ось — это как раз значение бита . Остаётся прибавить срез «бит выключен» к срезу «бит включён»:
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. Такая версия при работает за доли секунды — Python перестаёт быть ограничением. Для надмасок меняются местами индексы: v[:, 0, :] += v[:, 1, :], для Мёбиуса — -= вместо +=.
Типичные ошибки
- Перепутать порядок циклов. Внешний цикл — по битам, внутренний — по маскам. Если сделать наоборот (для каждой маски перебрать биты), получится неправильный результат: часть подмасок посчитается несколько раз, часть не посчитается вовсе.
- Не скопировать массив.
F = aвместоF = a[:]испортит входные данные — обидно, еслиaнужен дальше (например, для свёртки). - Неверная разрядность. Если числа до , нужно бит, а не «сколько элементов в массиве». Дополнение
~xв Python отрицательное — используйтеfull ^ x, гдеfull = (1 << n) - 1. - Переполнение. Суммы по подмаскам растут быстро: — сумма всего массива. В C++ берите
long longили работайте по модулю. - Мёбиус с прибавлением. Обратное преобразование — это вычитание. Если «обращать» тем же
sos, получится двойное Зета, а не исходный массив. - Путать подмаски и надмаски. Перед кодом сформулируйте: нужен или . В задачах про AND обычно надмаски, про OR — подмаски.
Где встречается на собеседованиях
Честно: на обычном собеседовании в продуктовую компанию SOS DP почти не спрашивают. Это олимпиадная техника, она чаще встречается на Codeforces (Div. 1–2, задачи уровня D–E) и на AtCoder. Если на интервью дают задачу с битовыми масками, обычно хватает базовых битовых операций или перебора подмножеств.
Но знать SOS полезно по двум причинам. Во-первых, на собеседованиях в компании с сильным алгоритмическим фильтром и на олимпиадных отборах встречаются задачи «для каждого числа найти совместимое», где не проходит. Во-вторых, это хороший пример переиспользования идеи: если вы поняли, что сумма по подмаскам — это многомерная префиксная сумма, вы сможете объяснить решение интервьюеру за минуту, а не воспроизводить заученный код.
Признаки, что задача — на SOS:
- значения до или около того, а элементов много (до );
- в условии AND, OR или «является подмножеством»;
- нужно ответить «для каждого x» или посчитать что-то по всем маскам сразу;
- решение через перебор подмасок даёт , и это на грани.
Итог
- SOS DP — -мерная префиксная сумма на гиперкубе масок, вместо .
- Внешний цикл по битам, внутренний по маскам, одна строка обновления.
- Мёбиус — то же самое с вычитанием, он обращает Зета.
- Надмаски — зеркальная версия, нужна для задач про AND.
- Вместе Зета и Мёбиус дают OR- и AND-свёртку за .
Если ещё не знакомы с базой, начните с ДП по битовым маскам — там разобраны кодирование подмножеств и перебор подмасок, на которых строится эта статья.