Чем перебор подмасок (for sub = mask; ...) отличается по сложности от SOS DP — почему 3^n?
Видел идиому перебора всех подмасок маски:
for (int sub = mask; sub > 0; sub = (sub - 1) & mask) { ... }
Если так делать для каждой маски от 0 до $2^n - 1$, какая суммарная сложность? Почему говорят про $3^n$, а не $4^n$ или $2^n \cdot 2^n$?
2 ответа
Идиома sub = (sub - 1) & mask корректно перебирает все непустые подмаски mask по убыванию. Для одной маски с k установленными битами она делает $2^k$ итераций.
Суммарно по всем маскам: $\sum_{mask} 2^{popcount(mask)}$. Считаем комбинаторно — сколько масок имеет ровно k битов? $\binom{n}{k}$. Тогда:
$$\sum_{k=0}^{n} \binom{n}{k} \cdot 2^k = (1 + 2)^n = 3^n$$
(по биному Ньютона). Поэтому полный перебор всех подмасок всех масок — это $O(3^n)$, а не $4^n$.
Интуиция «$3^n$»: каждый бит независимо находится в одном из трёх состояний — «не в маске», «в маске и в подмаске», «в маске, но не в подмаске». Три варианта на бит → $3^n$.
for (int mask = 0; mask < (1 << n); ++mask)
for (int sub = mask; ; sub = (sub - 1) & mask) {
// обработка подмаски sub
if (sub == 0) break; // важно: 0 обрабатываем и выходим
}
Для $n=20$: $3^{20} \approx 3.5 \cdot 10^9$ — на грани TLE. Если задача сводится к сумме по подмаскам, SOS DP за $O(n\cdot 2^n)$ почти всегда лучше ($2\cdot10^7$ против $3.5\cdot10^9$).
Когда $3^n$ всё-таки нужен и оправдан: задачи вида «разбить множество на части» (set partition DP), где для каждой маски действительно надо перебрать все её разбиения на подмаску и дополнение — там $O(3^n)$ неизбежен, и для $n \le 18$ ($3^{18}\approx 4\cdot10^8$) это проходит. А SOS DP помогает только когда нужна именно агрегация (сумма/максимум) по подмаскам, а не индивидуальная обработка каждой пары (подмаска, дополнение).