[백준] 12850 본대 산책 2

문제 링크

http://icpc.me/12850

12850번: 본대 산책2

풀이

유배당한 불쌍한 정보대생을 위한 문제다..

분할 정복을 이용한 O(logN) 행렬 제곱을 이용하여 풀었다.

이 글을 참고하여 풀었다.

행렬 곱셈식을 곱씹어본다면 왜 이렇게 풀이할 수 있는지 알 수 있다.

Counting source to destination path of k length

 

코드

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using vl = vector<ll>;
using vvl = vector<vl>;
#define rep(i,a,b) for(int i = a; i < b; i++)

const ll mod = 1e9 + 7;

vvl mul(const vvl &a, const vvl &b) {
    vvl ret(8, vl(8, 0));
    rep(i, 0, 8) rep(j, 0, 8) rep(k, 0, 8) {
        ret[i][j] = (ret[i][j] + (a[i][k] * b[k][j]) % mod) % mod;
    }
    return ret;
}

vvl pw(vvl a, int n) {
    vvl ret(8, vl(8, 0));
    rep(i, 0, 8) ret[i][i] = 1;
    while (n) {
        if (n % 2) ret = mul(ret, a);
        a = mul(a, a);
        n >>= 1;
    }
    return ret;
}

int main() {
    vvl a = {
        {0, 1, 0, 0, 0, 0, 0, 1},
        {1, 0, 1, 0, 0, 0, 1, 0},
        {0, 1, 0, 1, 0, 1, 1, 0},
        {0, 0, 1, 0, 1, 1, 0, 0},
        {0, 0, 0, 1, 0, 1, 0, 0},
        {0, 0, 1, 1, 1, 0, 1, 0},
        {0, 1, 1, 0, 0, 1, 0, 1},
        {1, 0, 0, 0, 0, 0, 1, 0}
    };
    int n; cin >> n;
    a = pw(a, n);
    cout << a[4][4];
}