[For competition professionals] Summary of doubling

When to use

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

image.png

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

Recommended Posts

[For competition professionals] Summary of doubling
Binary search summary for competition professionals
[For competition professionals] Run-length compression summary
[For competition professionals] Minimum spanning tree summary
[For competition professionals] Union Find Tree Summary
Summary of methods for automatically determining thresholds
Summary of various for statements in Python
Library organization of competition professionals ~ enumeration of divisors ~
Summary of petit techniques for Linux commands
Summary of useful techniques for Python Scrapy
Confirmation of basics of competition professionals ~ gcd and lcm ~
Summary of frequently used Python arrays (for myself)
Numerical summary of data
Summary of Tensorflow / Keras
Summary of useful tips for Linux terminals ☆ Updated daily
Library organization of competition professionals ~ Two-dimensional linear indefinite equation ~
Summary of pyenv usage
Summary of python environment settings for myself [mac] [ubuntu]
Summary of tools for operating Windows GUI with Python
Summary of pre-processing practices for Python beginners (Pandas dataframe)
A brief summary of Linux antivirus software for individuals
[Competition Pro] Summary of stock buying and selling problems
Summary of Python arguments
Summary for learning RAPIDS
Summary of logrotate software logrotate
Summary of test method
[For beginners] Summary of standard input in Python (with explanation)
Summary of stumbling blocks in Django for the first time
Summary of Hash (Dictionary) operation support for Ruby and Python
Summary of yum packages required for pip install on EC2
[For beginners] A word summary of popular programming languages (2018 version)
Summary of python file operations
Summary of Python3 list operations
2017.3.6 ~ 3.12 Summary of what we did
Convenient usage summary of Flask
Summary of Linux distribution types
Percentage of LIKE for pymysql
Overview of Docker (for beginners)
Pipenv usage summary (for myself)
Basic usage of Pandas Summary
A brief summary of Linux
Summary of Proxy connection settings
Implementation of Scale-space for SIFT
A brief summary of Graphviz in python (explained only for mac)
Summary of recommended APIs for artificial intelligence, machine learning, and AI
Summary of pages useful for studying the deep learning framework Chainer
[For beginners] Summary of suffering from kaggle's EDA and its struggle