题目大意是一个3N的棋盘，用12的骨牌覆盖的方案数

使用一个三位的二进制数表示状态，则可以有：

n行：000 ……………………………………. 000

n-1行：000 001 010 011………………… 111

为避免状态重复，我们不允许在n-1行上平放骨牌（因为等会由n-1行转移的第n行时，我们可以在n行上平放），所以我们可以构造一个矩阵来表示这些转移（具体自己画一画就知道了），即可以得到以下矩阵A：

0000000100000010000001000000100100010000001000000100000110010010然后求A的n次幂，A^n[7][7]就是我们要的答案啦～

至于矩阵方面的一些知识，可以看一下Matrix67的这篇文章：十个利用矩阵乘法解决的经典题目

//
//  main.cpp
//  p2663
//
//  Created by Silly on 13-12-26.
//  Copyright (c) 2013年 Silly. All rights reserved.
//

#include
#include
#include

using namespace std;

typedef long long  ll;

const ll  mat[8][8] = {
    {0, 0, 0, 0, 0, 0, 0, 1},
    {0, 0, 0, 0, 0, 0, 1, 0},
    {0, 0, 0, 0, 0, 1, 0, 0},
    {0, 0, 0, 0, 1, 0, 0, 1},
    {0, 0, 0, 1, 0, 0, 0, 0},
    {0, 0, 1, 0, 0, 0, 0, 0},
    {0, 1, 0, 0, 0, 0, 0, 1},
    {1, 0, 0, 1, 0, 0, 1, 0},
};

struct ma {
    ll a[8][8];
};

ma res, tmp;

ma mm(ma x, ma y) {
    ma z;
    memset(z.a ,0 , sizeof(z.a));
    for (int i = 0; i < 8; i++) {
        for (int j = 0; j < 8; j++) {
            for (int k = 0; k < 8; k++) {
                z.a[i][j] += x.a[i][k] * y.a[k][j];
            }
        }
    }
    return z;
}

ma mp(int x) {
    ma z;
    if (x == 1) {
        return res;
    }
    z = mp(x / 2);
    z = mm(z, z);
    if (x % 2 != 0) {
        z = mm(res, z);
    }
    return z;
}

int main(int argc, const char * argv[])
{
    int n;
    cin >> n;
    while (n != -1) {
        if (n == 0) {
            cout << 1 << endl;
            cin >> n;
            continue;
        }
        memset(res.a, 0, sizeof(res.a));
        memset(tmp.a, 0, sizeof(tmp.a));
        for (int i = 0; i < 8; i++) {
            for (int j = 0; j < 8; j++) {
                res.a[i][j] = mat[i][j];
            }
        }
        tmp = mp(n);
        printf("%lldn", tmp.a[7][7]);
        cin >> n;
    }
    return 0;
}