[DP] 행렬 거듭제곱(power matrix), 빠른 거듭제곱 알고리즘

일반적인 dp에서 진화한 형태이다.

 

import numpy as np
import sys

def multiply_matrix(A, B, mod):
    A = np.array(A)
    B = np.array(B)
    result = np.dot(A, B) % mod
    return result.tolist()

def power_matrix(A, p, mod): #빠른 거듭제곱 알고리즘
    if p == 1: 
        return A
    if p % 2: #n이 홀수라면, 기본 행렬을 n-1번 거듭제곱한 후, 그 결과에 기본 행렬을 한 번 더 곱한다.
        return multiply_matrix(A, power_matrix(A, p-1, mod), mod)
    half = power_matrix(A, p//2, mod)   #n이 짝수라면, 기본 행렬을 n/2번 거듭제곱하고, 자기 자신과 곱한다.
    return multiply_matrix(half, half, mod)

def mushroom(n):
    MOD = 1000000007
    if n == 1:
        return 1
    base_matrix = [[1, 1], [1, 0]]
    result_matrix = power_matrix(base_matrix, n-1, MOD)
    return (result_matrix[0][0] + result_matrix[0][1]) % MOD

a = int(sys.stdin.readline())
print(mushroom(a))  # 예제 입력1

 

피보나치 수열의 dp[i]와 dp[i-1]의 합을 구하는 문제이다.

base matrix는 1,1로 시작한다. 이는 dp[1]과 dp[0]이 각각 1,1이기 때문이다.

 

power_matrix함수에 해당 매트릭스를 넣으면 n이 짝수라고 가정했을 때, n-1이 들어가므로 p%2가 0이 된다.

고로 multiply matrix 함수에 들어간다. A와 그 이전(n-1)의 power matrix가 B로 들어가게 된다.

 

아니라면 p//2번째가 들어가고, 이게 빠른 거듭제곱 알고리즘이 된다.

 

빠른 거듭제곱 알고리즘

 

원래 a^1023을 구하려면 a를 1023번 곱해야 한다.

그러나 빠른 거듭제곱을 사용하면 다르다.

 

“빠른 거듭제곱” 알고리즘은 다음과 같이 작동합니다:

거듭제곱의 지수 n이 짝수인지 홀수인지 확인합니다.
만약 n이 짝수라면, 기본 행렬을 n/2번 거듭제곱한 후, 그 결과를 자기 자신과 곱합니다.
만약 n이 홀수라면, 기본 행렬을 n-1번 거듭제곱한 후, 그 결과에 기본 행렬을 한 번 더 곱합니다.

 

이러면 거듭제곱의 지수를 절반으로 줄여나가면서 거듭제곱을 계산할 수 있게 된다.

 

def multiply_matrix(A, B, mod):
    A = np.array(A)
    B = np.array(B)
    result = np.dot(A, B) % mod
    return result.tolist()

 

 

multiply matrix는 풀어 쓰면 위와 같다.

한마디로 A,B의 dot(행렬곱)을 계산하고, 전체 array에 대해서 mod로 나눠준 값이다.

 

다른 형태로는 순열의 개수가 있다.

import sys

def apply_permutation(permutation, cards):
    # 주어진 순열을 카드 배열에 적용하여 새 배열을 반환
    n = len(permutation)
    new_cards = [0] * n
    for i in range(n):
        new_cards[permutation[i]] = cards[i]
    return new_cards

def multiply_permutations(p1, p2):
    # 두 순열 p1과 p2를 곱하여 결과 순열을 반환
    n = len(p1)
    result = [0] * n
    for i in range(n):
        result[i] = p1[p2[i]]
    return result

def permutation_power(permutation, k, n):
    # 순열을 k번 적용한 결과 순열을 반환
    result = list(range(n))  # 단위 순열 (identity permutation)
    base = permutation[:]
    
    while k > 0:
        if k % 2 == 1:
            result = multiply_permutations(base, result)
        base = multiply_permutations(base, base)
        k //= 2
    
    return result

def main():

    N, K = map(int, input().split())
    A = list(map(int, input().split()))

    # A는 1-based index, 이를 0-based index로 변환
    permutation = [a - 1 for a in A]
    
    # K번 순열을 계산
    final_permutation = permutation_power(permutation, K, N)
    
    # 초기 카드 배열 [1, 2, ..., N]에 최종 순열 적용
    initial_cards = list(range(1, N + 1))
    final_cards = apply_permutation(final_permutation, initial_cards)
    
    # 결과 출력
    print(" ".join(map(str, final_cards)))

# 예제 입력이 주어지는 경우 아래와 같이 테스트 가능
# 예제 실행을 위해 주석 해제하고 필요한 입력을 주어야 합니다.
main()