[BOJ-2749]피보나치수3

이전에 푼 10830번 문제[행렬제곱] 를 이 문제를 위해 먼저 풀이한 건데 

이거는 정방행렬을 어떻게 만드는지에 대한 것이 핵심이었다...

예전에 정방행렬 만들어 놓고나서 이렇게 하면 되겠다... 하고 안풀어서..

튜터링하는데 이문제를 넣어두기는 했다. 물론 어느정도까지는 구하는데 시간이 걸려도 memory error 이런 거는 안받겠는데 이 문제는 보통의 방식으로 풀게되면 memory error를 받을 것 같다.

피보나치수3 을 풀기전 

https://www.acmicpc.net/problem/10830

10830번: 행렬 제곱

www.acmicpc.net

이 문제를 먼저 풀어보는 게 좋을 것 같다.

이 문제에 대한 자세한 내용은 BOJ에 올라와 있는 내용이 정리가 잘되어있다..

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] % 1000000
    return new_mat
 
 
 
expo = [1]
for i in range(1, 18*3+200):
    expo.append(2 * expo[len(expo) - 1])
 
mat_size = 2
mat_squa = input()
mat = [[1,1],[1,0]]
 
mat_square_list = []
mat_square_list.append(mat)
for step in range(0, 18*3+100):
    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] %= 1000000
    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
 
print ans_mat[1][0]