백준[13976] 타일 채우기 2

문제 설명

문제 링크

http://icpc.me/13976

13976번: 타일 채우기 2

풀이

dp와 분할 정복을 이용하여 풀이할 수 있다.

분할 정복을 이용한 행렬의 빠른 거듭제곱은 곱셈을 풀면서 공부하자.

dp점화식은 dp[n] = 3*dp[n-2] + sum(dp[k]) (k는 n-4부터 0까지 k-=2)

위의 식에 n-2를 대입한식과  위의 식을 빼면 dp[n] = 4 * dp[n-2] -  dp[n-4]가 나온다.

행렬식으로 표현하면 위와 같이 표현할 수 있다. 이제 위의 행렬식을 분할정복을 이용하여 빠르게 계산하면 된다.

코드

#include <cstdio>
#include <vector>

using namespace std;
using ll = long long;
using vl = vector<ll>;
using vll = vector<vl>;

const ll mod = 1e9 + 7;

vll operator*(vll &a, vll &b) {
    vll ret(2, vl(2));
    for (int i = 0; i < 2; i++) {
        for (int j = 0; j < 2; j++) {
            for (int k = 0; k < 2; k++) {
                ret[i][j] += a[i][k] * b[k][j] % mod;
                ret[i][j] = (ret[i][j] + mod) % mod;
            }
        }
    }
    return ret;
}

int main() {
    ll n; scanf("%lld", &n);
    vll A = {{4, -1}, {1, 0}};
    vll initial = {{1, 0}, {1, 0}};
    vll ans = {{1, 0}, {0, 1}};
    if (n & 1) {
        printf("0");
    } else {
        n /= 2;
        while (n) {
            if (n & 1) ans = ans * A;
            A = A * A;
            n /= 2;
        }
        ans = ans * initial;
        printf("%lld", ans[0][0] % mod);
    }
}