[Python] Binary Acing 2020D

Acing 2020D

X is so large that it cannot be simply simulated. Here, the popcount of X is at most N, so the value of X divided by the popcount is always less than N. Also, when Xi is inverted, the popcount of such an integer is equal to (X's popcount ± 1). Therefore, for all numbers from 1 to N, divide them by popcount and replace them too much to find the number of operations until it becomes 0, and then for each digit such that Xi = 1, (X). If you find the sum of too much divided by (popcount + 1) of and the sum of too much divided by (popcount-1 of X), f (Xi) will be calculated as f (Xi) if Xi is 1. The sum of the remainders divided by)-2 ^ i divided by (popcount-1 of X) is calculated, and this is divided by (popcount-1 of X) to obtain a number less than N. Similarly, if Xi is 0, find the sum of the remainders divided by (X popcount + 1) + 2 ^ i divided by (X popcount + 1), and divide this by (X popcount + 1). You can get a number less than N by dividing by). From the above, it was found that the number of operations required to reach 0 can be determined by O (1) for each Xi.

Here, regarding the amount of calculation for calculating the number of operations for all numbers from 1 to N, the number of popcounts of 2 * 10 ^ 5 or less is at most 18, and the number of popcounts of 18 or less is at most 4, 4 or less. You can see that the popcount is at most 2, the number of popcounts less than 2 is at most 1, and it reaches 0 in a maximum of 5 operations. Therefore, it can be said that the number of operations can be calculated for all numbers from 1 to N by O (NlogN), and it was found that this problem can be solved by O (NlogN). However, note the case where the X popcount is 0 or 1.

Sample code

n = int(input())
x = input()
 
#Original popcount
original_pop_count = x.count('1')
#Invert-1count
one_pop_count = original_pop_count - 1
#Invert+1count
zero_pop_count = original_pop_count + 1
 
#Residual in each ± 1
if one_pop_count == 0:
  one_mod = 0
else:
  one_mod = int(x, 2) % one_pop_count
zero_mod = int(x, 2) % zero_pop_count
 
#Precalculation of f
f = [0] * 220000
pop_count = [0] * 220000
for i in range(1, 220000):
    pop_count[i] = pop_count[i//2] + i % 2
    f[i] = f[i % pop_count[i]] + 1
 
#Precalculation of pow2
one_pow2 = [1] * 220000
zero_pow2 = [1] * 220000
for i in range(1, 220000):
    if one_pop_count != 0:
        one_pow2[i] = one_pow2[i-1] * 2 % one_pop_count
    zero_pow2[i] = zero_pow2[i-1] * 2 % zero_pop_count
    
# n-1, n-2, ,, 0
for i in range(n-1, -1, -1):
    if x[n-1-i] == '1':
        if one_pop_count != 0:
            nxt = one_mod
            # - 2^i % 2
            nxt -= one_pow2[i]
            nxt %= one_pop_count
            print(f[nxt] + 1)
        else:
            print(0)
    if x[n-1-i] == '0':
        nxt = zero_mod
        nxt += zero_pow2[i]
        # + 2^i % 2
        nxt %= zero_pop_count
        print(f[nxt] + 1)