분할 정복을 이용한 행렬 거듭제곱을 통해 선형 점화식 DP 해결하기

사실 이 글을 임시글에 담아놓은 지 2달 정도 되었으나 이제야 글을 쓴다.

더 늦추어지면 계속 글을 쓸지 않을 것 같아 미완성 글을 올린다.

피보나치 수열과 같이 구하는 값이 선형 점화식 형태를 띄고 있을 때

우리는 분할 정복을 이용한 행렬 거듭제곱을 빠른 시간 내에 구해

원하는 값을 구할 수 있다.

1. 피보나치 수 6

BOJ 피보나치 수 6

피보나치의 수의 점화식이 $F_n=F_{n-1}+F_{n-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}$

$F_0=0,\;F_1=1$ 인점을 통해

$\begin{bmatrix} F_n \\ F_{n-1} \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-1}\begin{bmatrix} F_1=1 \\ F_0=0 \end{bmatrix}$

이제 행렬의 거듭제곱을 계산해주면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
#define MOD (int)(1e9+7)
typedef long long ll;
using namespace std;

vector<vector<ll>> a(2,vector<ll> (2,1)),ans(a);

void solve(ll c){
    if(c<=1) return;
    if(c%2!=0){
        solve(c/2);
        vector<vector<ll>> tmp(ans);
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                ans[i][j]=(tmp[i][0]*tmp[0][j])%MOD;
                ans[i][j]=(ans[i][j]+tmp[i][1]*tmp[1][j])%MOD;
            }
        }
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                tmp[i][j]=ans[i][j];
            }
        }
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                ans[i][j]=(tmp[i][0]*a[0][j])%MOD;
                ans[i][j]=(ans[i][j]+tmp[i][1]*a[1][j])%MOD;
            }
        }
    }
    else{
        solve(c/2);
        vector<vector<ll>> tmp(ans);
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                ans[i][j]=(tmp[i][0]*tmp[0][j])%MOD;
                ans[i][j]=(ans[i][j]+tmp[i][1]*tmp[1][j])%MOD;
            }
        }
    }
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    a[1][1]=ans[1][1]=0;
    ll n;
    cin >> n;
    solve(n-1);
    cout << ans[0][0];
    return 0;
}

2. 리그 오브 레전설(Large)

BOJ 리그 오브 레전설(Large)

처음에 롤 관련 문제인줄 알고 북마크에 담아놓은 지 1년 정도 된 문제이다. ㅋㅋㅋ

처음에는 $N$ 범위를 고려하지 않고

같은 것이 있는 순열임을 고려해

1차원 DP로 접근했으나

$N$의 범위가 너무 커서

내가 모르는 다른 방법이 있는 줄 알고 답을 봤다.

문제 접근

$i$초를 스킬 분배로 나누는 경우는

$i-1$에서 스킬 $A$를 쓰는 경우랑

$i-M$에서 스킬 $B$를 쓰는 경우 두 가지 경우에서 올 수 있으므로

다음과 같은 점화식을 얻을 수 있다.

$DP[i]=DP[i-1]+DP[i-M]$

이제 우리는 이 점화식을 행렬 점화식으로 나타내야 한다.

$DP[i]$를 재사용하지 않는 방법으로 점화식을 나타내야하므로

$DP[i]$부터 $DP[i-M]$을 모두 사용해야 한다.

이를 고려하면 다음과 같은 행렬 점화식을 생각해낼 수 있다.

($DP[i]$를 $D_i$로 표현하겠다.)

$\begin{bmatrix} D_n\\ D_{n-1}\\ D_{n-2}\\ ...\\ D_{n-M+1} \end{bmatrix}$ = $\begin{bmatrix} 1 & 0 & 0 & \cdot\cdot\cdot & 0 & 1\\ 1 & 0 & 0 & \cdot\cdot\cdot & 0 & 0\\ 0 & 1 & 0 & \cdot\cdot\cdot & 0 & 0\\ \cdot\cdot\cdot\\ 0 & 0 & 0 & \cdot\cdot\cdot & 1 & 0 \end{bmatrix}\begin{bmatrix} D_{n-1}\\ D_{n-2}\\ D_{n-3}\\ ...\\ D_{n-M} \end{bmatrix}$

이를 일반항으로 나타내주면 다음과 같다.

$\begin{bmatrix} D_n\\ D_{n-1}\\ D_{n-2}\\ ...\\ D_{n-M+1} \end{bmatrix}$ = $\begin{bmatrix} 1 & 0 & 0 & \cdot\cdot\cdot & 0 & 1\\ 1 & 0 & 0 & \cdot\cdot\cdot & 0 & 0\\ 0 & 1 & 0 & \cdot\cdot\cdot & 0 & 0\\ \cdot\cdot\cdot\\ 0 & 0 & 0 & \cdot\cdot\cdot & 1 & 0 \end{bmatrix}^{n-M+1}\begin{bmatrix} D_{M-1}=1\\ D_{M-2}=1\\ D_{M-3}=1\\ ...\\ D_{0}=1 \end{bmatrix}$

이제 분할정복을 이용한 행렬 제곱을 수행해주면 된다.

코드는 다음과 같다.

#include <bits/stdc++.h>
#define MOD 1000000007
typedef long long ll;
using namespace std;

ll n,m;

void solve(vector<vector<ll>> &a, vector<vector<ll>> &b, ll c){
    if(c==1) return;
    solve(a,b,c/2);
    vector<vector<ll>> tmp(m,vector<ll> (m,0));
    for(int i=0;i<m;i++){
        for(int j=0;j<m;j++){
            for(int k=0;k<m;k++){
                tmp[i][j]=(tmp[i][j]+a[i][k]*a[k][j]%MOD)%MOD;
            }
        }
    }
    if(c%2){
        for(int i=0;i<m;i++){
            for(int j=0;j<m;j++){
                a[i][j]=0;
                for(int k=0;k<m;k++){
                    a[i][j]=(a[i][j]+tmp[i][k]*b[k][j]%MOD)%MOD;
                }
            }
        }
    }
    else for(int i=0;i<m;i++) for(int j=0;j<m;j++) a[i][j]=tmp[i][j];
}


int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    cin >> n >> m;
    if(m>=n){ cout << 1+(m==n); return 0; }
    vector<vector<ll>> a(m,vector<ll> (m,0));
    a[0][0]=1;
    a[0][m-1]=1;
    for(int i=1;i<m;i++) a[i][i-1]=1;
    vector<vector<ll>> b(a);
    solve(a,b,n-m);
    ll ans=a[0][0];
    for(int i=0;i<m;i++) ans=(ans+a[0][i])%MOD;
    cout << ans;
    return 0;
}

참고 블로그 : driip.me