“How many ways….” suggests a combinatorical counting, i.e., mostly a recursive/DP problem.

Now we need to find generation step and states between generation steps

Insight

1. Since we want to generate numbers < K, then the prefix matters more than suffix, i.e., the steps should go from left to right

2. Consider A and B independently, i.e., consider the case with only A and K

3. Each step is moving 1 bit at a time. If we fit the prefix of A, then we have constraints on which bit A can offer, otherwise, we know the
new bit from A can be either 0 or 1, because the prefix is < A already, prefix + 1s will be less than A regardless

4. similar to 3), we can apply similar argument to K, if we know we match the prefix of K,
we have to consider the value of K, to decide if we can generate 0 or 1, if prefix < K already, prefix +1s will be less than K regardlesso

5. generate 0 bit is the safe case, it is the use of 1 that requires special attention

Therefore, the states we need to know are

1. which bit we are at

2. Is the partial-number generated by A matching prefix of A

3. Is the partial-number generated by B matching prefix of B

4. Is the partial-number generted by 2) and 3) matching prefix of K

Implementation details

1. initial state is ways(31, true, true, true)

2. base state is ways(0, bool, bool, bool)

3. Note that if we follow the if conditions and if the current bit is 1 or 0, the # of branch clauses grow very quickly. Instead, let us
think: in what condition can we use the (A, B, K) combo (0,0,0), (1, 0, 0), (0, 1, 0), (1,1,1). Note that because ABit & BBit = KBit, we
need to check only 4 possible cases, and add the result if they could be applicable