[Python] Binary Acing 2020D

Acing 2020D

X ist so groß, dass es nicht einfach simuliert werden kann. Hier beträgt die Popanzahl von X höchstens N, sodass der Wert von X geteilt durch die Popanzahl immer kleiner als N ist. Wenn Xi invertiert wird, ist der Popcount einer solchen Ganzzahl gleich (X's Popcount ± 1). Teilen Sie sie daher zunächst für alle Zahlen von 1 bis N durch Popcount und ersetzen Sie sie zu stark, um die Anzahl der Operationen zu ermitteln, bis sie 0 wird, und dann für jede Ziffer, sodass Xi = 1, (X) Wenn Sie die Summe von zu viel geteilt durch Popcount + 1) und die Summe von zu viel geteilt durch (Popcount-1 von X) finden, wird f (Xi) als f (Xi) berechnet, wenn Xi 1 ist. Die Summe der Reste geteilt durch) -2 ^ i geteilt durch (popcount-1 von X) wird berechnet, und dies wird geteilt durch (popcount-1 von X), um eine Zahl kleiner als N zu erhalten. Wenn Xi 0 ist, finden Sie in ähnlicher Weise die Summe der Summe des Restes geteilt durch (X Popcount + 1) + 2 ^ i geteilt durch (X Popcount + 1) und dividieren Sie diese durch (X Popcount + 1). Sie können Zahlen kleiner als N erhalten, indem Sie durch) teilen. Aus dem Obigen wurde herausgefunden, dass für jedes Xi die Anzahl von Operationen, die erforderlich sind, um 0 zu erreichen, durch O (1) bestimmt werden kann.

Hier beträgt der Rechenaufwand zur Berechnung der Anzahl der Operationen für alle Zahlen von 1 bis N höchstens 18 und die Anzahl der Popcounts von 18 oder weniger höchstens 4, 4 oder weniger. Sie können sehen, dass der Popcount höchstens 2 beträgt, die Anzahl der Popcounts unter 2 höchstens 1 beträgt und in maximal 5 Vorgängen 0 erreicht. Daher kann gesagt werden, dass O (NlogN) verwendet werden kann, um die Anzahl von Operationen für alle Zahlen von 1 bis N zu berechnen, und es wurde festgestellt, dass dieses Problem durch O (NlogN) gelöst werden kann. Beachten Sie jedoch den Fall, in dem die X-Anzahl 0 oder 1 beträgt.

Beispielcode

n = int(input())
x = input()
 
#Original Popcount
original_pop_count = x.count('1')
#Umkehren-1count
one_pop_count = original_pop_count - 1
#Umkehren+1count
zero_pop_count = original_pop_count + 1
 
#Rest in jeweils ± 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
 
#Vorberechnung von 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
 
#Vorberechnung von 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)