## ยง 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; ) {
}
}
```

- 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 `t`

since `t[i]=s[i]=1`

. - Thus, for all indexes
`i > x`

we have `c[i]=s[i]`

.