Suffix Flip

for each number, precalcuate the binary flip of that number

for each number, we have no more that 17 bits to flip, so we can populate a DP table

Overall 10^5 * 17

Official solution

Note that at every move, the last digit keeps changing between 0 and 1, alternatively, until we reach the all 0 cases.

Therefore, all numbers end with 0 => losing case. The other is the winning case.

Falling Balls

Segment tree related