lsc4719   2달 전

안녕하세요, 아주대학교 컴공과 학생입니다.

알고리즘 수업시간에 F[n] = F[n-1] + F[n-2], F[1]=0, F[2]=1 점화식이 있을 때, [[0, 1], [1, 1]] ^ n = [[F[n-1], F[n]], [F[n], F[n+1]] 라고 배웠습니다.

그래서 궁금증이 생겼는데요,

임의의 Homogeneous linear recurrence가 주어졌을 때, 저렇게 오른쪽처럼 생긴, 행렬의 거듭제곱 = ? 꼴의 등식을 항상 구할 수 있을까요?

그러면 DP 문제 풀때 O(lg n) 만에 풀 수 있을 것 같아요.

lsc4719   2달 전

수업끝나고 교수님한테 여쭤봤는데, 교수님도 모르겠다고 하시네여.

wwiiiii   2달 전

97b7143af9713f03cb1a51b71a24e0d0.png

이렇게 되지 않을까요?

lsc4719   2달 전

답변 감사해요 ㅎㅎ

적어주신 등식을 이용하면, O(k^3 lg n) 만에 임의의 homogeneous linear recurrence의 n번째항을 계산할 수 있네요.

감솨감솨합니다 ^^

lsc4719   2달 전

(수정) k -> m

lsc4719   2달 전

놀랍게도, 이번 ACM-ICPC 예선 D번이 이 문제와 동일했네요!!

댓글을 작성하려면 로그인해야 합니다.