[PYTHON] [Für Wettkampfprofis] Zusammenfassung der Verdoppelung

Wann zu verwenden

• Wenn der N-te Zustand gefunden wird, in dem dieselbe Operation wiederholt wird. (Insbesondere wenn ein Element mehrere Elemente enthält und diese ineinander übergehen)

Was ist gut

Normalerweise ist es möglich, die Stelle, an der die Reihenfolge von O (N) vom Ende genommen wird, auf O (log N) zu verkürzen. Die iterative Quadratmethode ist auch eine Art davon. Es ist großartig, dass O (XlogN) unterdrückt werden kann, wenn alle Ergebnisse von N Operationen an mehreren X-Elementen wie oben beschrieben erhalten werden.

Was ist zu tun

Die Idee ist die gleiche wie bei der iterativen Quadratmethode. Das zweite Ergebnis aus dem ersten Ergebnis, das vierte Ergebnis aus dem zweiten Ergebnis und so weiter. Notieren Sie sich den Status nach jeder Operation in einem Array (er wird zweidimensional, wenn mehrere Elemente gleichzeitig betrieben werden) (so etwas wie dp?).

Bild

Denken

Wenn die N-te Zeit durch genau 2 ^ k dargestellt werden kann, kann die Liste direkt referenziert werden, aber wenn sie zu einem Bruch wird, wird die N-te Zeit durch wiederholtes Verweisen auf das konstruierte Array angegeben. zB) Das 5. Mal kann unter Bezugnahme auf das Ergebnis des 1. Males nach Bezugnahme auf das Ergebnis des 4. Males ausgegeben werden. Die Bitarithmetik beeinflusst diesen Prozess.

Wie viele Bits fallen bei der Konvertierung in Bits auf?

a = []
for i in range(int(math.log2(K)) + 1):
    if K>>i & 1:
        a.append(i)

Vorlage

Erstellen Sie eine Tabelle, um nach N Operationen von X Elementen zu suchen.

#Zweidimensionale Array-Erstellung
dv = []
for _ in range(int(math.log2(K)) + 1):
    l = [0] * X
    dv.append(l)

# dv[0][0:X]Initialisieren

#Bauen Sie einen Tisch mit Verdoppelung
for k in range(1, int(math.log2(K)) + 1):
    for n in range(N):
        dv[k][n] = dv[k - 1][dv[k - 1][n]]

Anwendungsbeispiel

Wiederholte quadratische Methode

Wiederholte quadratische Methode

MOD = 10 ** 9 + 7

def mod_pow(x: int, n: int):
    bi = str(format(n, "b"))
    res = 1
    a = x
    for i in range(len(bi)):
        if n >> i & 1:
            res = (res * a) % MOD
        a = (a * a) % MOD
    return res

ABC167 D - Teleporter

Ungefähr um diese Zeit 10 ^ 18 ≒ 2 ^ 60, so dass Sie bis zu 60 sehen können. Sie können auch jedes Mal "log2 (K) + 1" berechnen.

def main():
    N, K = map(int, input().split())
    A = [int(i) for i in input().split()]

    dv = []
    for _ in range(60):
        l = [0] * N
        dv.append(l)
    
    for n in range(N):
        dv[0][n] = A[n] - 1
    
    for k in range(1, 60):
        for n in range(N):
            dv[k][n] = dv[k - 1][dv[k - 1][n]]
    
    a = []
    for i in range(60):
        if K>>i & 1:
            a.append(i)

    now = 0
    for i in a:
        now = dv[i][now]
    print(now + 1)

Ich habe TLE mit Python gemacht, also mit PyPy.

ABC136 D - Gathering Children

10 ** 100 (googol) O (XlogN) zum zweiten Mal ist ebenfalls eng. Am Ende müssen Sie nur den Zustand des Hin- und Hergehens zwischen RLs wiederholen, sodass Sie sich nur um die Chancen und Chancen der Anzahl der Operationen kümmern müssen. Selbst wenn alle Fälle bis auf das rechte Ende von S wie R sind, kann man sehen, dass die letzte Phase erreicht werden kann, indem die maximale Anzahl von Zeichen 10 ** 5 Mal gedreht wird.

# log2(10 ** 5) ≒ 16.6 → Endlich ans[17][]Sollte erhalten werden.
LOG = 18

def main():
    S = input()
    N = len(S)
    to = []
    for _ in range(LOG):
        l = [0] * N
        to.append(l)
    
    for i in range(N):
        to[0][i] = i + 1 if S[i] == "R" else i - 1
    
    for i in range(1, LOG):
        for j in range(N):
            to[i][j] = to[i - 1][to[i - 1][j]]

    ans = [0] * N
    for j in range(N):
        ans[to[LOG - 1][j]] += 1

    L = [str(i) for i in ans]
    print(" ".join(L))
    return

Referenz

• https://www.akiradeveloper.com/post/algorithm-doubling/#%E3%83%80%E3%83%96%E3%83%AA%E3%83%B3%E3%82%B0
• https://ikatakos.com/pot/programming_algorithm/contest_history/atcoder/2019/0804_abc136
• https://www.hamayanhamayan.com/entry/2019/08/07/204315