백준 10830

문제 링크

문제 설명.

행렬의 n제곱을 한 결과를 출력하는 문제이다.(각각의 원소는 1000으로 나누었을 때의 나머지.)

input으로는 두 수 A,B, 그리고 이후에 차례대로 AxA행렬이 하나 주어진다.

# example from 문제
3 3  # A B
1 2 3
4 5 6
7 8 9  # 3x3 행렬

풀이 코드.

from sys import stdin

n,m = map(int,stdin.readline().strip().split())
mat = [list(map(int,stdin.readline().strip().split())) for _ in range(n)]

# I_{n,n}
result = [[0]*n for _ in range(n)]
for i in range(n):
    result[i][i] = 1

# 연산 정의
def mat_mult(mat1,mat2,n):
    result = [[0]*n for _ in range(n)]
    for i in range(n):
        for j in range(n):
            tmp = 0
            for k in range(n):
                tmp += mat1[i][k]*mat2[k][j]
            result[i][j] = tmp%1000
    
    return result

#계산
while m != 0:
    if m%2 == 1:
        result = mat_mult(mat,result,n)
    
    m = m//2
    mat = mat_mult(mat,mat,n)
    
for i in result:
    print(*i)

짧은 문제 설명과 마찬가지로 설명할 것도 길지 않다. 이전 문제와 비슷하게 거듭제곱에 따라 곱을 해주는 연산이 약간 달라진다. 이 경우 연산을 한번 하는데 필요한 시간비용이 필연적으로 크게 드는 편이라 이전 문제와 다르게 단위를 2로 쪼겠다.(쓰면서 드는 생각은 bitmasking을 이용해도 좋았을 것 같다는 생각이?)

잡담

아ㅏㅏㅏㅏㅏㅏ 예비군 가기 싫다..
글을 쓰고 있는 것이 시간이 너무 오래 걸리는 것은 매우 단점이다..