§ DP over submasks

• https://codeforces.com/contest/1554/problem/B
• 5e8 operations is 1
• take every (mask, submask). The bits of the pair can be 1 1, 1 0, and 0 0. So the pairs of all mask, submask will be 3^n

for(int m = N; m >= 0; m--) {
  for(int s = m; s = (s- 1) & m; ) {
    // get all submasks.
  }
}

• let s be a submask of m. [for arbitrary bits abc with the 1 shown being the rightmost 1, followed by all zeroes. ]
• Consider the largest submask of m smaller than s, call it t. We wish to show that t = (s-1)&m = abc011.
• t is clearly a submask of m, since it is a submask of s.
• We wish to show that t=(s-1)&m is the greatest submask of m smaller than s.
• For contradiction, suppose s > c > t and c is a submask of m.
• Let x be the index of the rightmost 1 in s ( x marks the spot). So s is of the form s[n]s[n-1]...s[x]s[x-1]...s[0] where s[x]=1 and s[x-1]=s[x-2]=...=s[0]=0. So we can write s = s[n]s[n-1]...;x:1;00..0
• Now t is of the form t = t[n]t[n-1]...;x:0;00..0.
• Any number c < s must have for all indeces i > x such that s[i] = 0 implies c[i] = 0.
• If c is such that for some index i > x where s[i]=1 we have c[i]=0, then such a number will be less that tsince t[i]=s[i]=1.
• Thus, for all indexes i > x we have c[i]=s[i].