Hi Codeforces, I would like to share some thoughts regarding a way of understanding SOS DP (This might already exist). Usually whenever I try to read about blogs on SOS DP, I find it a bit hard to comprehend the idea, why this simple 2 nested for loops works:

for(int i = 0;i < N; ++i) {
   for(int mask = 0; mask < (1<<N); ++mask) {
	if(mask & (1<<i)) {
		F[mask] += F[mask^(1<<i)];
        }
   } 
}

Lets try to solve a simpler problem:

Given a mask $$$M$$$ $$$(1 \leq M \lt 2^{20})$$$ , generate all its submasks (via recursion)

Solution:

• We can iterate on bitwise (say from last bit to first bit)
• if current bit b is set, we have 2 cases, either set or unset bit b in my submask.
• if current bit b is unset, our submask also has this bit b as unset.

void gen_submask(int b , int curmask, int submask) {
    if(b < 0) {
        // basecase
        cout << submask << endl;
        return;
    }
    if(curmask&(1ll << b))  {
        gen_submask(b-1 , curmask , submask | (1ll << b)); // set
        gen_submask(b-1 , curmask , submask); // unset
    }
    else  {
        gen_submask(b-1 , curmask , submask); // unset
    }
}

gen_submask(19 , mask , 0);

the above simple recursive function would print all the submasks for a given mask.

Optimisation 1: The second and third parameters (current mask , sub mask) can be combined into a single parameter.
Reason: Since we iterate on bitwise from last to first bit, say I am currently on bit b, the last bits (LSB .. b+1) of current mask is not required for my further computation, since the submask has been generated for those bits.

Say we are at bit b, We could maintain (LSB ... b+1) bits for submask and (b .. 0) bits contain information of input mask. By this way, we would always get information of bit which is under process, and also maintain generated submask in same variable.

Visual for better understanding of the optimisation:

Optimised code:

void gen_submask(int b , int curmask) {  // current bit , current mask
    if(b < 0) {
        cout << curmask << endl;  // basecase
        return;
    }

    if(curmask&(1ll << b)) {  // if bit is set, we have 2 cases
        gen_submask(b-1 , curmask);                 // set
        gen_submask(b-1 , curmask ^ (1ll << b));    // unset
    }
    else {
        gen_submask(b-1 , curmask);                 // unset
    }
}

gen_submask(19 , mask);

This code is simpler to understand, and this prints all submasks, for a given input mask, which serves our purpose.
Just memoize this recursive function, thats it, SOS DP.

void gen_submask(int b , int curmask) {
    if(b < 0) {
        return F[curmask];
    }

    if(dp[b][curmask] != -1) return dp[b][curmask];

    ll ans = 0;
    if(curmask&(1ll << b)) {  
        ans += gen_submask(b-1 , curmask);
        ans += gen_submask(b-1 , curmask ^ (1ll << b));
    }
    else {
        ans += gen_submask(b-1 , curmask);
    }
    return dp[b][curmask] = ans;
}

Conclusion:

• Say any problem related to Sum of Subsets, Supersets, (or any variation of it) we could write a simple recursive function to generate all valid masks (as per the problem) and memoize it using DP.

Examples:

• F(Mask) = Sum of all Masks, such that (odd bits are subset, even bits are superset)

[UPD] There is another interpretation of SOS DP, using higher dimensional prefix sums, Thanks to Misuki for the idea. Click Here