변형 피보나치 수열의 행렬 점화식Permalink

다음과 같은 점화식을 보자.

여기서 $A=1,~B=1,~k=2$ 라면 일반 피보나치 수열이다.

이 문제를 그냥 푸는것보다 피보나치 수열꼴의 점홧기에 $A,B,k$ 값이 달라졌을 때 행렬을 어떻게 구성할 수 있는지 살펴보자.

이 글에선 위와 같은 꼴을 다룰 뿐이지만, 결국 위와 같은 선형 점화식 대한 행렬을 구성함에 있어 이해를 돕는다.

이 글에서 다루진 않지만 더 고급 개념인 키타마사법이나 벌레캠프 메시를 이해하는데도 도움이 될 것이다.

일반 피보나치 수열에 쓰이는 행렬을 살펴보자.

여기서 $A, B$ 를 추가해보자.

라 하자.

단순히 $1$행의 $1, 1$을 $A, B$로 바꾸는 것으로 원하는 결과를 만들었다.

$f(n-k)$ 란 값이 등장하기 위해 $k$행 $k$열의 행렬이 필요하다는 것을 유추할 수 있다.

결국 최종 점화식은 다음과 같다.

이런식으로 행렬을 구성하면 $O(k^3 \log n)$ 에 문제를 해결할 수 있다.

연습 문제Permalink

BOJ 17272 - 리그 오브 레전설 (Large)

를 구하는 문제이다.