백준 10830 풀이 (행렬 제곱, 분할 정복, 거듭제곱)

이번 문제는 이전문제들을 이용하여 풀면 아주 쉽게 풀 수 있다.

1. 분할 정복을 이용하여 거듭제곱을 구할수 있다.

2. 행렬제곱을 구할수 있다.

이 2가지가 가능하면 상당히 쉬운 문제이다. 그런데 정답률이 낮고 solved.ac에서 골드4인것은 좀 의문이다.

 

문제를 보면 행렬에 대해서 제곱을 하는 문제이다.

행렬을 제곱한다는것은 같은 놈을 여러번 곱한다는 소리다. 만약 행렬을 A라고 한다면 분할 정복을 이용하여 n을 아주 빠르게 구할 수 있다. 

$$ A^n = A^{n/2}*A^{n/2}$$

$$ A^{n/2}=A^{n/4}*A^{n/4}$$

위의 식을 이용하면 분할하여 빠르게 A의 n승 행렬을 구할수 있다.

단, n이 홀수인 경우에는 n이 정확히 나누어 떨어지지 않기 때문에

$$ A^n = A^{n/2}*A^{n/2}*A$$

로 계산해 주면된다.  

 

그리고 행렬 곱셈은 이전 문제 guccin.tistory.com/72을 참고하면 된다. 그냥 for구문으로 해결하면 된다.

백준 2740 풀이 (행렬 곱셈)

 

이제 코드를 작성하면 아래와 같다.

n,s = map(int, input().split())
t = []
for i in range(n):
    t.append(list(map(int, input().split())))

def calc(t, s):
    if s == 1:
        for i in range(len(t)):
            for j in range(len(t)):
                t[i][j] %= 1000
        return t
    t2 = calc(t, s//2)
    # 제곱을 해준다.
    tmp = [[0 for i in range(len(t2))] for i in range(len(t2))]
    for i in range(len(t2)):
        for j in range(len(t2)):
            for n in range(len(t2)):
                tmp[i][j] += t2[i][n] * t2[n][j]
                tmp[i][j] %= 1000
    if s % 2 == 1: # 홀수 (곱 한번더)
        tmp2 = [[0 for i in range(len(t2))] for i in range(len(t2))]
        for i in range(len(t2)):
            for j in range(len(t2)):
                for n in range(len(t2)):
                    tmp2[i][j] += tmp[i][n] * t[n][j]
                    tmp2[i][j] %= 1000
        return tmp2
    else: #짝수 (바로 리턴)
        return tmp
for i in calc(t,s):
    for j in i:
        print(j, end=' ')
    print()