Atcoder ->D - Anything Goes to Zero

can any one help with the question :
question :click
how to approach or please share your ideas…???

Handle the cases in which the count of ‘1’ is less than equal to 1. Now, let’s say there were 'K number of ‘1’ in original string ‘S’. Notice that after each flip value of ‘K’ can become either ‘K+1’ or ‘K-1’.
So, Find the value of ‘S’ modulo ‘K’, ‘S’ modulo ‘K+1’ and ‘S’ modulo ‘K-1’, This can be done in O(N) using

After this notice that on each bit flip you add either 2^i modulo (K+1) or subtract 2^i modulo (K-1) so just find the remainders. Notice that all these remainders are less than equal to (N+1) since K <= N.

Also pre-compute the values of f() for all N <= 10^5(using simple brute force). Then use these precomputed values to answer the values of the above found remainders.

1 Like

wow!thanks for the approach…!

can you share the code…?