SOS DP (Sum over Subsets)
O(2^n · n)For every mask, accumulate f over all of its submasks, in O(2^n·n) instead of the naive O(3^n) or O(4^n). One bit position per round: after round i, dp[m] has summed everything reachable by clearing bits among the first i. Flip the direction of the inner update to get sum over supermasks. This is the tool behind 'count pairs with x & y == 0' style problems.
// use it on
Codeforces 165E: Compatible Numbers ↗
For each a[i], find any a[j] with a[i] & a[j] == 0: store each value at its own mask, run SOS over the complement, and each query is a lookup. Max over submasks instead of sum; the recurrence is identical.
// the code
// dp[m] starts as f[m]; ends as sum of f over all submasks of m
vector<long long> sos(vector<long long> dp, int n) { // 2^n entries
for (int i = 0; i < n; i++)
for (int m = 0; m < (1 << n); m++)
if (m >> i & 1) dp[m] += dp[m ^ (1 << i)];
return dp;
}
// sum over SUPERmasks: if bit i is 0, dp[m] += dp[m | (1 << i)]
// max/min over submasks: replace += with max=/min=// more bitmask