[PYTHON] [For competition professionals] Summary of doubling

When to use

• When finding the Nth state in which the same operation is repeated. (Especially when there are multiple elements in one aspect and they transition to each other)

What is good

Normally, the place where the order of O (N) is taken from the end can be shortened to O (log N). Repeated squares is also a type of this. It is great that O (XlogN) can be suppressed when all the results of N operations on multiple X elements as described above are obtained.

What to do

The idea is the same as the iterative square method. The second result from the first result, the fourth result from the second result, and so on. Make a note of the state after each operation in an array (it becomes two-dimensional when operating multiple elements at the same time) (something like dp?).

image

Thinking

If the Nth time can be expressed by exactly 2 ^ k, the list can be referred directly, but if it becomes a fraction, the Nth time is issued by repeatedly referring to the constructed array. eg) The 5th time can be issued by referring to the result of the 1st time after referring to the result of the 4th time. Bit operations are influential in this process.

How many bits stand out when converted to bits

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

template

Create a table to find after N operations of X elements.

#Two-dimensional array creation
dv = []
for _ in range(int(math.log2(K)) + 1):
    l = [0] * X
    dv.append(l)

# dv[0][0:X]Initialize

#Build a table with doubling
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]]

Example of use

Repeated squares

Repeated squares

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

About this time, 10 ^ 18 ≒ 2 ^ 60, so you can see up to 60. You can also calculate log2 (K) + 1 each time.

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)

I did TLE with Python, so with PyPy.

ABC136 D - Gathering Children

10 ** 100 (googol) It's hard even with O (XlogN) seeking the first time. In the end, you only have to repeat the state of going back and forth between RLs, so you only have to worry about the even or odd number of operations. Furthermore, even if all the cases except the right end of S are like R, it can be seen that the final phase can be reached by turning the maximum number of characters 10 ** 5 times.

# log2(10 ** 5) ≒ 16.6 → Finally ans[17][]Should be obtained.
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

reference

• 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