[BOJ-10830]행렬제곱

행렬의 제곱을 구하는 문제이다. 

행렬의 크기는 정방행렬로 n*n n~[2,5] 까지 주어지며 

제곱 수는 1e+11 까지 주어진다. 

처음에 문제를 풀 때, 예제입력을 넣어도 

입력

2 5
1 2
3 4

69 558
337 406

출력인데

? A^4 만 되어도 저 수를 넘어가는데 왜 값이 저렇게 나오냐 이생각 했었는데

또 문제 제대로 안 읽었다. 1000으로 나누었을 때 나머지를 출력으로 내보내야 한다고...

.... 생각해보니 큰 수의 문제라면... 좀 어려워지고, 메모리도 솔직히 말이 안될 것 같다는 생각이 들기는 했다.

여튼.,. 문제를 잘못읽고 다시 제대로 읽고나서 코드를 작성하였다. 

내가 이문제를 접근하였을 때 제곱이 엄청 큰 수 가 되는데 어떻게 구할 수 있을까? 라는 생각을 먼저했고,

제곱을 구하기 위해서는 각 자신에게 자신을 곱하면 제곱이 되므로 이것을 

으로 2^n 까지 행렬을 구해둔 다음, 가장 큰 이진수 부터 빼며 요구하는 제곱꼴을 구하는 방식으로 작성을 하였다. 

코드가 너무 더러운데.. 다른 사람은 진짜 간결하게 짜기는 했던데... 하... 1900B 되는 길이인데 다른 사람코드는 300B-400B... 이었던 이뻤던 코드가 있었다...

def f_mat_square(mat_size, mat):
    new_mat = [[0 for i in range(mat_size)] for j in range(mat_size)]
    for arow in range(0, mat_size):
        for acol in range(0, mat_size):
            for brow in range(0, mat_size):
                new_mat[arow][acol] += mat[arow][brow] * mat[brow][acol]
    return new_mat
 
 
 
def f_mat_product(m1,m2,mat_size):
    new_mat = [[0 for i in range(mat_size)] for j in range(mat_size)]
    for arow in range(mat_size):
        for acol in range(mat_size):
            for brow in range(mat_size):
                new_mat[arow][acol] += m1[arow][brow] * m2[brow][acol]
 
    for row in range(mat_size):
        for col in range(mat_size):
            new_mat[row][col] = new_mat[row][col] % 100000
    return new_mat
 
 
 
expo = [1]
for i in range(1, 50):
    expo.append(2 * expo[len(expo) - 1])
 
user_input = map(int, raw_input().split())
 
mat_size = user_input[0]
mat_squa = user_input[1]
mat = []
for step in range(0, mat_size):
    line = map(int, raw_input().split())
    mat.append(line)
 
mat_square_list = []
mat_square_list.append(mat)
for step in range(0, 40):
    new_mat = f_mat_square(mat_size, mat)
    for row in range(0, mat_size):
        for col in range(0, mat_size):
            new_mat[row][col] %= 100000
    mat_square_list.append(new_mat)
    mat = new_mat
 
index = len(mat_square_list)
ans_mat = [[0 for i in range(mat_size)] for j in range(mat_size)]
for row in range(mat_size):
    for col in range(mat_size):
        if(row == col):
            ans_mat[row][col] = 1
while(mat_squa > 0):
    if(mat_squa >= expo[index]):
        mat_squa -= expo[index]
        ans_mat = f_mat_product(ans_mat, mat_square_list[index], mat_size)
    elif(mat_squa < expo[index]):
        index -= 1
 
for row in range(mat_size):
    for col in range(mat_size):
        print ans_mat[row][col]%1000,
    print