[Python] Acing binaire 2020D

Acing 2020D

X est si grand qu'il ne peut pas être simplement simulé. Ici, le popcount de X est au plus N, donc la valeur de X divisée par le popcount est toujours inférieure à N. De plus, lorsque Xi est inversé, le popcount d'un tel entier est égal à (popcount de X ± 1). Par conséquent, d'abord pour tous les nombres de 1 à N, divisez-les par popcount et remplacez-les trop pour trouver le nombre d'opérations jusqu'à ce qu'il devienne 0, puis pour chaque chiffre tel que Xi = 1, (X) Si vous trouvez la somme de trop divisé par (popcount + 1) de et la somme de trop divisée par (popcount-1 de X), f (Xi) sera calculée comme f (Xi) si Xi est 1. La somme des restes divisée par) -2 ^ i divisé par (popcount-1 de X) est calculée, et elle est divisée par (popcount-1 of X) pour obtenir un nombre inférieur à N. De même, si Xi est égal à 0, trouvez la somme du reste divisée par (X popcount + 1) + 2 ^ i divisé par (X popcount + 1), et divisez-la par (X popcount + 1) Vous pouvez obtenir des nombres inférieurs à N en divisant par). D'après ce qui précède, il a été constaté que pour chaque Xi, le nombre d'opérations nécessaires pour atteindre 0 peut être déterminé par O (1).

Ici, à propos de la quantité de calcul pour calculer le nombre d'opérations pour tous les nombres de 1 à N, le nombre de popcount de 2 * 10 ^ 5 ou moins est au plus de 18, et le nombre de popcount de 18 ou moins est au plus de 4, 4 ou moins. Vous pouvez voir que le popcount est au plus de 2, le nombre de popcount de moins de 2 est au plus de 1, et il atteint 0 dans un maximum de 5 opérations. Par conséquent, on peut dire que O (NlogN) peut être utilisé pour calculer le nombre d'opérations pour tous les nombres de 1 à N, et il a été constaté que ce problème peut être résolu par O (NlogN). Cependant, notez le cas où le popcount X est 0 ou 1.

Exemple de code

n = int(input())
x = input()
 
#Popcount d'origine
original_pop_count = x.count('1')
#Inverser-1count
one_pop_count = original_pop_count - 1
#Inverser+1count
zero_pop_count = original_pop_count + 1
 
#Résiduel dans chaque ± 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
 
#Pré-calcul de 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
 
#Pré-calcul de 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)