1696C. Fishingprince plays with array [thinking questions + intermediate state + optimized storage]

analysis

Give me a list, If the number inside is m Multiples of can be split into m individual x // m, Similarly, if you encounter m Same. x, It can be reduced to mx
ask a Can it become b
Think ：a and b If it can be expanded into c, Then there must be a - > c -> b（ Because shrinking and releasing are relative ）
So we put a and b Just expand , But if there is no brain expansion, it will explode memory
So we can record the same continuous number , Use a two-dimensional representation , And then look at it [-1] Of num Whether it is the same as the current one
If yes, add [-1] Otherwise append([num, cnt])

ac code

import sys
input = sys.stdin.readline


def expand(lst, m):
    c = []
    for num in lst:
        cnt = 1
        while num % m == 0:
            num //= m
            cnt *= m
        if len(c) == 0:
            c.append([num, cnt])
        elif c[-1][0] == num:
            c[-1][1] += cnt
        else:
            c.append([num, cnt])
    return c

for _ in range(int(input())):
    n, m = list(map(int, input().split()))
    a = list(map(int, input().split()))
    k = int(input())
    b = list(map(int, input().split()))

    # op1 and op2 are reversible
    # if a and b can both expand to c(mid state)
    # then a -> c -> b

    a = expand(a, m)
    b = expand(b, m)
    #print(a)
    #print(b)

    if a == b:
        print('Yes')
    else:
        print('No')

summary

Thinking questions + a become b We'll consider whether we can a and b All become c Then the allowed operation is reversible + Optimize storage （ Record the same number of consecutive occurrences ）