행렬 제곱

백준 11444 풀이 (피보나치 수 6, 분할 정복, 행렬 제곱)

이 문제 정말 엄청난 삽질을 했다. 심지어 풀지도 못해서 풀이 찾아보니 아주 잘 정리한 식이 있었다. 그걸 사용하는 건가 보다. 이걸 사전지식 없이 어떻게 푼다는건지 정말 똑똑한 사람들...... 처음 접근은 예전에 페르마의 소정리를 이용해서 풀려고 했다. 위키백과에 피보나치를 구하는 일반항이 존재했다. 생긴게 마치 예전에 풀었던 문제랑 비슷해서 비슷한 방식으로 2^n*5**0.5를 p-2승 해서 풀려고 했다. 그런데 문제가 루트때문인지 음수 제곱때문인지 자꾸 수가 망가져서 나누어 떨어지지도 않고 계산이 안되었다. 더구나 n승 만큼 제곱을 해주면 inf값이 나와서 계산이 안됐다. 그래서 삽질을 한참하다가 고수들 풀이를 구경갔더니 피사노 주기라는 키워드도 알게 되었고, 행렬제곱으로 피보나치를 구하는 일반항..

백준 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/..