SOS DP
SOS DP means Sum Over Subsets dynamic programming. Given a value for every bitmask, it calculates the sum over all submasks of every mask in instead of .
The same transform can use minimum, maximum, count, or another associative combine operation.
We have bits and a value for every mask. For every mask, calculate
Enumerating all submasks separately takes
That is too slow around .
Start with . Process bits one by one. When processing bit , every mask containing that bit receives the value of the same mask with bit removed:
After processing the first bits, dp[mask] contains contributions from masks that may differ from mask only in those processed positions. After all bits, every submask is allowed.
Each submask contribution follows exactly one path through the bit decisions, so it is counted once.
Algorithm:
The two loops perform additions.
Imagine opening one switch at a time. Once bit is processed, a mask collects answers from both possibilities for that bit: kept or removed.
For three bits, start with in mask order.
For mask 111, the final value contains all eight original masks. For mask 101, only 000, 001, 100, and 101 contribute.
The input contains and values in increasing mask order.
f on the right side: the transition needs partially accumulated dp values.1. Copy f into dp.
2. For every bit b from 0 to n - 1:
1. For every mask from 0 to 2^n - 1:
1. If bit b is set in mask:
- add dp[mask without bit b] to dp[mask].
3. Print dp.
#include <bits/stdc++.h>
#define fi first
#define se second
using namespace std;
void solve() {
int n;
cin >> n;
int size = 1 << n;
vector<long long> dp(size);
for (int mask = 0; mask < size; mask++) {
cin >> dp[mask];
}
for (int bit = 0; bit < n; bit++) {
for (int mask = 0; mask < size; mask++) {
if (mask & (1 << bit)) {
dp[mask] += dp[mask ^ (1 << bit)];
}
}
}
for (int mask = 0; mask < size; mask++) {
cout << dp[mask] << " \n"[mask + 1 == size];
}
}
int32_t main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
solve();
return 0;
}