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

Задача: для каждой маски $i$ посчитать

$$P[i] = \sum_{j \subseteq i} F[j].$$

Наивно это $3^n$ — перебор подмасок каждой маски. Есть способ за $O(2^n \cdot n)$, и он состоит из трёх строк.

for (int bit = 0; bit < n; bit++)
    for (int mask = 0; mask < (1 << n); mask++)
        if (mask >> bit & 1) p[mask] += p[mask ^ (1 << bit)];

Почему это верно

Инвариант: после обработки битов $0, \dots, b$ величина $p[mask]$ равна сумме $F[j]$ по тем подмаскам $j$, которые отличаются от $mask$ только этими битами.

В начале ($b = -1$) это верно: $p[mask] = F[mask]$. Шаг: обрабатывая бит $b+1$, для масок с этим битом мы прибавляем сумму по маскам, у которых он снят. Учтённые наборы битов объединяются, и инвариант сохраняется.

После всех $n$ битов условие «отличаются только этими битами» становится пустым ограничением — учтены все подмаски.

Это в точности префиксные суммы по каждому измерению, только измерений $n$ и каждое двоичное. Отсюда и название приёма: сумма по подмножествам, sum over subsets.

Замер: при $n = 20$ преобразование занимает 9 мс против 2674 мс у перебора подмасок, при $n = 18$ — 2 мс против 265 мс.

Порядок циклов

Внешний цикл — по битам, внутренний — по маскам. Если поменять местами, ответ станет неверным, причём на маленьких тестах часто совпадёт: при $n = 1$ он верен всегда, при $n = 2$ угадывает примерно в одном случае из десяти, при $n = 3$ — примерно в одном из двухсот (проверено на 10 000 случайных наборов для каждого $n$).

Причина: при внешнем цикле по маскам значение $p[mask]$ уже содержит вклад младших битов, и слагаемые учитываются повторно.

Обратное преобразование

По $P$ восстановить $F$ можно тем же кодом с минусом:

for (int bit = 0; bit < n; bit++)
    for (int mask = 0; mask < (1 << n); mask++)
        if (mask >> bit & 1) f[mask] -= f[mask ^ (1 << bit)];

Развернув все шаги, получим формулу обращения Мёбиуса на решётке подмножеств:

$$F[i] = \sum_{j \subseteq i} (-1)^{|i| - |j|} P[j],$$

где $|i|$ — число единичных битов. Прямо по ней считать не надо: это снова $3^n$.

Четыре варианта

что считаем	условие	знак
сумма по подмаскам	mask >> bit & 1	+=
обращение по подмаскам	mask >> bit & 1	-=
сумма по надмаскам	!(mask >> bit & 1), берём mask | (1 << bit)	+=
обращение по надмаскам	то же	-=

Выпишите их рядом хотя бы раз: путают их чаще, чем ошибаются в чём-то более сложном.

Где применяется

Считать пары с условием на маски. Например, количество пар с $a_i ;\&; a_j = 0$: посчитать, сколько элементов является подмаской каждой маски, и для каждого $a_i$ взять значение на дополнении.

Свёртка по подмножествам. $c[m] = \sum_{i \cup j = m,\ i \cap j = \varnothing} a[i] b[j]$ считается за $O(2^n n^2)$ через суммы по подмаскам с разбиением по числу битов.

Включение-исключение по признакам. Когда «хотя бы один признак» считается через «ровно эти признаки», обратное преобразование даёт переход между ними.

Смежное

• Подмаски;
• Префиксные суммы — тот же приём в одном измерении;
• Рюкзак и суммы.