백준) 12878 Blocks

https://www.acmicpc.net/problem/12878

Blocks

n=1일때와 n=2일때 어떻게 전개되는지를 생각해보니 금방 풀 수 있었다.

	상태
경우의 수	빨강	노랑	추가->
a	짝	짝	빨	홀	짝	c	2a+b+c
			주	짝	짝	a
			노	짝	홀	b
			초	짝	짝	a
b	짝	홀	빨	홀	홀	d	a+2b+d
			주	짝	홀	b
			노	짝	짝	a
			초	짝	홀	b
c	홀	짝	빨	짝	짝	a	a+2c+d
			주	홀	짝	c
			노	홀	홀	d
			초	홀	짝	c
d	홀	홀	빨	짝	홀	b	b+c+2d
			주	홀	홀	d
			노	홀	짝	c
			초	홀	홀	d

따라서 n개일 때 경우의 수들에 행렬을 곱해 n=1일 때 경우의 수들을 구할 수 있다.

그래서 결국 4*4 행렬을 구하는 문제로 바뀌는데, n이 십억까지므로, 2^x승들의 행렬들을 미리 구하는 분할정복으로 풀 수 있다.

#include <iostream>
#include <math.h>
#include <string.h>
using namespace std;
 
#define m 10007
typedef long long ll;
 
ll n;
ll origin[4][4] = 
{ 
{2,1,1,0},
{1,2,0,1},
{1,0,2,1},
{0,1,1,2} };
 
ll mat[30][4][4];
 
int main() {
    memcpy(mat[0], origin, sizeof(origin));
 
    cin >> n;
    ll tmp[4][4];
    int d = 1;
    while ((ll(1) << d) <= n) {
        for (int i = 0; i < 4; ++i) {
            for (int j = 0; j < 4; ++j) {
                ll t = 0;
                for (int k = 0; k < 4; ++k) {
                    t = (t + (mat[d - 1][i][k] * mat[d - 1][k][j]) % m) % m;
                }
                tmp[i][j] = t;
            }
        }
 
        memcpy(mat[d++], tmp, sizeof(tmp));
    }
 
    int dd = 0;
    int arr[4] = { 1,0,0,0 };
    while ((ll(1) << dd) <= n) {
        int tmp[4];
        if (n & (ll(1) << dd)) {
            for (int i = 0; i < 4; ++i) {
                tmp[i] = 0;
                for (int j = 0; j < 4; ++j)
                    tmp[i] = (tmp[i] + (mat[dd][i][j] * arr[j]) % m) % m;
            }
 
            memcpy(arr, tmp, sizeof(tmp));
        }
        dd++;
    }
 
    cout << arr[0] % m;
}