⚡

행렬 거듭제곱을 이용한 선형 점화식의 DP 풀기

Date
2020/04/15
Tags
PS
Tutorial
Created by
Table of Contents

개요

DP 점화식이 이전의 항 몇 개의 선형결합으로 나타내지는 경우, 즉 선형방정식의 꼴일 경우, n번째 항 ana_n을 행렬 거듭제곱을 이용하여 O(m3log(n))O(m^{3}log(n)) 시간에 빠르게 구할 수 있다.
an=∑k=1mck⋅an−k=c1⋅an−1+c2⋅an−2+⋯+cm⋅an−m\begin{aligned} a_n&=\sum_{k=1}^{m}c_{k}\cdot a_{n-k}\\ &=c_1\cdot a_{n-1}+c_2\cdot a_{n-2}+\cdots +c_m\cdot a_{n-m} \end{aligned}

선행 지식

분할 정복을 이용한 빠른 행렬 거듭제곱 O(logN)O(logN)

내가 생각하는 순서

점화식을 도출하거나, 잘 짜맞췄더니 점화식이 개요에서 설명했던 저런 꼴이 될 경우, 나는 보통 이 순서대로 생각한다.
우리가 처음으로 만들 식은 대충
[FnFn−1⋮Fk]=[11…110…0⋮⋮⋱00…0][Fn−1Fn−2⋮Fk−1]\begin{bmatrix} F_{n}\\ F_{n-1}\\ \vdots\\ F_{k}\\ \end{bmatrix}= \begin{bmatrix} 1&1&\dots&1\\ 1&0&\dots&0\\ \vdots&\vdots&\ddots&\\ 0&0&\dots&0\\ \end{bmatrix} \begin{bmatrix} F_{n-1}\\ F_{n-2}\\ \vdots\\ F_{k-1}\\ \end{bmatrix}
이러한 꼴이 될 것이다. 편의상 우변의 행렬곱에서 왼쪽 행렬을 AA, 오른쪽 행렬을 BB라 하자. 
[FnFn−1⋮Fk]=[11…110…0⋮⋮⋱00…0]⏟A[Fn−1Fn−2⋮Fk−1]⏟B\begin{bmatrix} F_{n}\\ F_{n-1}\\ \vdots\\ F_{k}\\ \end{bmatrix}= \underbrace{ \begin{bmatrix} 1&1&\dots&1\\ 1&0&\dots&0\\ \vdots&\vdots&\ddots&\\ 0&0&\dots&0\\ \end{bmatrix} }_{A} \underbrace{ \begin{bmatrix} F_{n-1}\\ F_{n-2}\\ \vdots\\ F_{k-1}\\ \end{bmatrix} }_{B}
이 때, 우변은 M×MM\times M 행렬과 M× 1M\times 1 행렬의 곱이 되며, 당연히 그 결과는 M× 1M\times 1 행렬이다. (행렬 크기 MM은 풀이에 따라 달라질 수 있다)
좌변의 첫 행 FnF_{n}의 값이 Fn=…F_{n}=\dots 꼴의 점화식이 나오도록 AA의 첫 행을 적절히 잡는다. AA의 첫 행과 BB를 잘 생각하여, BB의 어떤 항을 살리고 어떤 항을 죽여야 하는지, 계수가 붙어있다면 고려하며 숫자를 채워넣는다.
좌변의 나머지 행에 대해서도 AA의 나머지 행을 잘 맞춰준다. 아마 첫 행인 FNF_{N}만 완성했다면 그 이후는 자기 자신이 등장하도록 적절히 하나만 트리거해주면 될 것이다. 이렇게 하여 AA 행렬을 완성한다.
우변에서 AA 행렬을 거듭제곱할 때마다 BB의 원소들의 차수가 하나씩 줄어든다. AA 행렬을 몇 번 거듭제곱하여야 BB가 nn에 종속적이지 않게 되는지, 고정된 숫자로 나올 수 있는지 계산한다.
식이 완성되었다면, 빠른 행렬 거듭제곱과 행렬곱만 잘 해주면 끝난다.
예제로 다시 한 번 살펴보자.

Remind: 피보나치 수

nn번째 피보나치 수 FnF_{n}을 행렬을 이용해 로그 시간에 구하는 방법은 익히 알려져 있다.
Fn=Fn−1+Fn−2F_{n}=F_{n-1}+F_{n-2} 인데, 우선 FnF_{n}에 주목해 보자.
FnF_{n}을 Fn−1F_{n-1}과 Fn−2F_{n-2} 두 개의 항으로 나타내야 하므로, 좌변과 BB 행렬을 적절히 잡아보자.
[FnFn−1]=[…]⏟A[Fn−1Fn−2]⏟B\begin{bmatrix} F_{n}\\F_{n-1} \end{bmatrix}= \underbrace{ \begin{bmatrix} \dots \end{bmatrix} }_{A} \underbrace{ \begin{bmatrix} F_{n-1}\\F_{n-2} \end{bmatrix} }_{B}
좌변에서 FnF_{n}을 점화식대로 맞춰주려면, AA의 첫 행을 어떻게 채우면 될까?
[FnFn−1]=[11□□][Fn−1Fn−2]\begin{bmatrix} F_{n}\\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1&1\\ \square&\square \end{bmatrix} \begin{bmatrix} F_{n-1}\\ F_{n-2} \end{bmatrix}
1, 1로 채우면, 좌변의 첫 행의 원소에 Fn=Fn−1+Fn−2F_{n}=F_{n-1}+F_{n-2} 점화식대로 결과값이 들어가게 된다.
좌변의 Fn−1F_{n-1}이 남는데, 얘는 BB에서 그대로 가져오면 된다. 그렇게 하려면 AA 행렬의 나머지를 어떻게 채우면 될까?
[FnFn−1]=[1110][Fn−1Fn−2]\begin{bmatrix} F_{n}\\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix} \begin{bmatrix} F_{n-1}\\ F_{n-2} \end{bmatrix}
1, 0으로 채우면 Fn−1=Fn−1F_{n-1}=F_{n-1}이다. 말 그대로이다. 일단 기본적인 식이 완성되었다. 여기서 조금만 더 변형을 가해보자. 우변의 BB의 차수를 하나씩 줄여나간다고 생각하면 편하다.
우변의 맨 앞에 AA를 하나 곱하면, BB의 모든 항의 차수가 하나씩 줄어들게 된다. 
 n=4n=4인 경우를 생각해보자. 써 보면 다음과 같다.
[F4F3]=[1110][F3F2]\begin{bmatrix} F_{4}\\ F_{3} \end{bmatrix} = \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix} \begin{bmatrix} F_{3}\\ F_{2} \end{bmatrix}
여기서 우변의 맨 앞에 AA를 하나 더 곱하면?
[F4F3]=[1110]2[F2F1]\begin{bmatrix} F_{4}\\ F_{3} \end{bmatrix}= \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}^2 \begin{bmatrix} F_{2}\\ F_{1} \end{bmatrix}
뭐 이렇게 되겠다. BB의 원소들의 차수가 하나씩 줄어든 것을 확인할 수 있다. 한번 더 하면?
[F4F3]=[1110]3[F1F0]\begin{bmatrix} F_{4}\\ F_{3} \end{bmatrix}= \begin{bmatrix} 1&1\\ 1& 0\end{bmatrix}^3 \begin{bmatrix} F_{1}\\ F_{0} \end{bmatrix}
그런데, F1F_{1}과 F0F_{0}는 각각 1과 0으로 상수값이다. 따라서 마지막 식을 다시 써 보면,
[F4F3]=[1110]3[10]\begin{bmatrix} F_{4}\\ F_{3} \end{bmatrix}= \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}^3 \begin{bmatrix} 1\\ 0 \end{bmatrix}
모든 과정이 끝났다. 우변의 (세제곱된) AA는 빠른 행렬 거듭제곱을 이용하여 로그 시간에 구할 수 있고, 우변의 계산 결과인 2× 12\times 1 행렬의 첫 행의 원소가 우리가 구하는 F4F_{4}가 된다.
방금은 n=4n=4인 경우를 예로 들었는데, 이를 일반화하면 다음과 같은 식을 도출할 수 있다.
[FnFn−1]=[1110]n−1[10]\begin{bmatrix} F_{n}\\ F_{n-1} \end{bmatrix}= \begin{bmatrix} 1&1\\ 1&0 \end{bmatrix}^{n-1} \begin{bmatrix} 1\\ 0 \end{bmatrix}
재귀적이지 않은, 바로 계산 가능한 일반화된 식이 만들어진 것이다. 이 문단에서 설명한 방법으로 BOJ#2749 - 피보나치 수 3 (https://www.acmicpc.net/problem/2749)을 풀 수 있다.
다른 문제를 몇 개 풀어보자.

BOJ#14440 - 정수 수열

문제 링크: https://www.acmicpc.net/problem/14440
점화식은 문제에 주어져있듯 An=x×An−1+y×An−2A_{n}=x\times A_{n-1}+y\times A_{n-2} 이다.
AnA_{n}이 An−1A_{n-1}과 An−2A_{n-2} 두 개의 항으로 나타내어져 있으므로, 대충 틀을 잡아보자.
[AnAn−1]=[…]⏟A[An−1An−2]⏟B\begin{bmatrix} A_{n}\\ A_{n-1} \end{bmatrix}= \underbrace{ \begin{bmatrix} \dots \end{bmatrix} }_{A} \underbrace{ \begin{bmatrix} A_{n-1}\\ A_{n-2} \end{bmatrix} }_{B}
설명의 편의상 쓰는 AA와 문제에서 주어진 AnA_n은 다르다. 어떻게 쓰다 보니까 겹쳤네... 암튼 AnA_{n}이 점화식대로 계산되려면?
[AnAn−1]=[xy□□][An−1An−2]\begin{bmatrix} A_{n}\\ A_{n-1} \end{bmatrix}= \begin{bmatrix} x&y\\ \square&\square \end{bmatrix} \begin{bmatrix} A_{n-1}\\ A_{n-2} \end{bmatrix}
An−1A_{n-1}은 BB에서 그대로 가져다 쓰면 되니까, 1과 0으로 채워두면 An−1A_{n-1}만 살고 An−2A_{n-2}는 죽겠지?
[AnAn−1]=[xy10][An−1An−2]\begin{bmatrix} A_{n}\\ A_{n-1} \end{bmatrix}= \begin{bmatrix} x&y\\ 1&0 \end{bmatrix} \begin{bmatrix} A_{n-1}\\ A_{n-2} \end{bmatrix}
이제 차수를 줄여보자. BB의 차수를 적절히 줄여 고정된 식을 만드려면 AA를 몇 번 거듭제곱하면 될까?
[AnAn−1]=[xy10]n−1[A1A0]\begin{bmatrix} A_{n}\\ A_{n-1} \end{bmatrix}= \begin{bmatrix} x&y\\ 1&0 \end{bmatrix}^{n-1} \begin{bmatrix} A_{1}\\ A_{0} \end{bmatrix}
A1A_1과 A0A_0은 입력에서 주어진다. 끝!

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

FnF_{n}을 "nn초를 채울 수 있는 경우의 수"라 정의하면, 조금만 생각해서 다음과 같은 점화식을 생각해볼 수 있다.
Fn=Fn−1+Fn−mF_{n}=F_{n-1}+F_{n-m}
nn초까지 채운 경우의 수는, 마지막에서 1초 떼서 A 스킬 쓰는 경우의 수와 마지막에서 mm초 떼서 B 스킬 쓰는 경우의 수의 합이다. 끝자리 경우로 분할하는 DP와 비슷하다.
F0F_{0}은 1이라 하자.
FnF_n을 나타내는 우변의 항이 Fn−mF_{n-m}까지 등장하므로, FnF_{n}에 이를 나타내려면 우변의 BB에 Fn−1F_{n-1}부터 Fn−mF_{n-m}까지의 항이 모두 등장해야 한다. 조금만 생각해보면, 다음과 같은 틀이 나온다.
[FnFn−1Fn−2⋮Fn−m+1]=[…]⏟A[Fn−1Fn−2Fn−3⋮Fn−m]⏟B\begin{bmatrix} F_{n}\\ F_{n-1}\\ F_{n-2}\\ \vdots\\ F_{n-m+1} \end{bmatrix}= \underbrace{ \begin{bmatrix} \dots \end{bmatrix} }_{A} \underbrace{ \begin{bmatrix} F_{n-1}\\ F_{n-2}\\ F_{n-3}\\ \vdots\\ F_{n-m} \end{bmatrix} }_{B}
좌변과 BB의 항들이 어디까지 가는지 범위에 주의하자. BB 행렬이 Fn−1F_{n-1}부터 시작해서 Fn−2, Fn−3, ⋯ , Fn−mF_{n-2},\ F_{n-3},\ \cdots,\ F_{n-m}까지 나와야 하므로, 개수를 잘 세서 좌변에도 맞춰주면 된다.
좌변의 FnF_{n}에 점화식대로 꽂아주려면, AA의 첫 행은?
[FnFn−1Fn−2⋮Fn−m+1]=[100…01][Fn−1Fn−2Fn−3⋮Fn−m]\begin{bmatrix} F_{n}\\ F_{n-1}\\ F_{n-2}\\ \vdots\\ F_{n-m+1} \end{bmatrix}= \begin{bmatrix} 1&0&0&\dots &0&1\\ & & & & &\\ & & & & &\\ & & & & &\\ & & & & &\\ \end{bmatrix} \begin{bmatrix} F_{n-1}\\ F_{n-2}\\ F_{n-3}\\ \vdots \\ F_{n-m} \end{bmatrix}
좌변의 Fn−1F_{n-1}부터는 BB의 값을 그대로 갖다 쓰면 되니까, 적절히 살릴 걸 살리고 죽일 걸 죽이며 AA 행렬을 완성하자.
[FnFn−1Fn−2⋮Fn−m+1]=[100…01100…00010…00⋮⋮⋮⋱000…10][Fn−1Fn−2Fn−3⋮Fn−m]\begin{bmatrix} F_{n}\\ F_{n-1}\\ F_{n-2}\\ \vdots \\ F_{n-m+1} \end{bmatrix}= \begin{bmatrix} 1&0&0&\dots &0&1\\ 1&0&0&\dots &0&0\\ 0&1&0&\dots &0&0\\ \vdots & \vdots & \vdots & \ddots & & \\ 0&0&0&\dots &1&0\\ \end{bmatrix} \begin{bmatrix} F_{n-1}\\ F_{n-2}\\ F_{n-3}\\ \vdots \\ F_{n-m} \end{bmatrix}
n=4n=4의 예시를 들면, 다음과 같은 식이 완성된 셈이다.
[F4F3F2F1]=[1001100001000010][F3F2F1F0]\begin{bmatrix} F_{4}\\ F_{3}\\ F_{2}\\ F_{1} \end{bmatrix}= \begin{bmatrix} 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 \end{bmatrix} \begin{bmatrix} F_{3}\\ F_{2}\\ F_{1}\\ F_{0} \end{bmatrix}
이제 AA의 거듭제곱을 통해 BB의 차수를 줄여보자. F0F_0 미만의 항들은 편의상 0이라 가정하자. 최대한 줄이면 다음과 같다.
[F4F3F2F1]=[1001100001000010]4[F0000]\begin{bmatrix} F_{4}\\ F_{3}\\ F_{2}\\ F_{1} \end{bmatrix}= \begin{bmatrix} 1 & 0 & 0 & 1\\ 1 & 0 & 0 & 0\\ 0 & 1 & 0 & 0\\ 0 & 0 & 1 & 0 \end{bmatrix}^{4} \begin{bmatrix} F_{0}\\ 0\\ 0\\ 0 \end{bmatrix}
그래서, 이를 일반화해보면, 다음과 같은 식이 나온다.
[FnFn−1Fn−2⋮Fn−m+1]=[100…01100…00010…00⋮⋮⋮⋱000…10]n[100⋮0]\begin{bmatrix} F_{n}\\ F_{n-1}\\ F_{n-2}\\ \vdots\\ F_{n-m+1} \end{bmatrix}= \begin{bmatrix} 1 & 0 & 0 & \dots & 0 & 1\\ 1 & 0 & 0 & \dots & 0 & 0\\ 0 & 1 & 0 & \dots & 0 & 0\\ \vdots & \vdots & \vdots & \ddots & & \\ 0 & 0 & 0 & \dots & 1 & 0 \\ \end{bmatrix}^{n} \begin{bmatrix} 1\\ 0\\ 0\\ \vdots \\ 0 \end{bmatrix}
끝!

BOJ#16467 - 병아리의 변신은 무죄

이 문제는 바로 위에서 설명한 문제와 거의 동일하게 풀 수 있다. 앞부분만 설명하면 눈치챌지도 모르겠다.
FnF_n을 nn일 후의 병아리의 수라 하면, 다음 점화식이 성립한다.
Fn=Fn−1+Fn−k−1F_n=F_{n-1}+F_{n-k-1}
또 그 꼴이다! 선형방정식 꼴이고, 좌변 FnF_n은 Fn−1F_{n-1}과 Fn−k−1F_{n-k-1}의 합으로 나타난다. BB 행렬은 Fn−1, Fn−2, ⋯ , Fn−k−1F_{n-1},\ F_{n-2},\ \cdots,\ F_{n-k-1}이 모두 나타나겠고, 이 행렬의 길이만큼 좌변의 행렬이 정의될 것이다. 한번 써 보면 다음과 같다.
[FnFn−1Fn−2⋮Fn−k]=[…]⏟A[Fn−1Fn−2Fn−3⋮Fn−k−1]⏟B\begin{bmatrix} F_{n}\\ F_{n-1}\\ F_{n-2}\\ \vdots\\ F_{n-k} \end{bmatrix}= \underbrace{ \begin{bmatrix} \dots \end{bmatrix} }_{A} \underbrace{ \begin{bmatrix} F_{n-1}\\ F_{n-2}\\ F_{n-3}\\ \vdots\\ F_{n-k-1} \end{bmatrix} }_{B}
위에서 설명한 문제와 아예 동일하다. 이제 AA 행렬 채우고, BB 행렬의 차수를 줄여나가면 된다.

BOJ#13328 - Message Passing

비슷한 방법으로 풀리는 것 같은데 아직 안 풀어봤다 나중에 풀어보고 풀이 추가하기