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)
Recommended Posts