题目地址：POJ：3734 — Blocks

题目描述

Panda has received an assignment of painting a line of blocks. Since Panda is such an intelligent boy, he starts to think of a math problem of painting. Suppose there are N blocks in a line and each block can be paint red, blue, green or yellow. For some myterious reasons, Panda want both the number of red blocks and green blocks to be even numbers. Under such conditions, Panda wants to know the number of different ways to paint these blocks.
给一排砖块涂色，一共有红蓝绿黄4种颜色，要求最后红色和绿色砖块数一定是偶数，求合法的涂色方案数。

输入输出格式

输入格式：
The first line of the input contains an integer T(1≤T≤100), the number of test cases. Each of the next T lines contains an integer N(1≤N≤10^9) indicating the number of blocks.

输出格式：
For each test cases, output the number of ways to paint the blocks in a single line. Since the answer may be quite large, you have to module it by 10007.

输入输出样例

输入样例#1：

2
1
2

输出样例#1：

2
6

题解

我们用dp[i][0/1/2]表示涂到第i个砖块，当前红绿砖块分别全是奇数、一奇一偶、全是偶数时合法的方案数。我们可以通过下面的式子来转移。
\begin{matrix} dp[i][0] = 2dp[i - 1][0] + dp[i - 1][1] \\ dp[i][1] = 2dp[i - 1][0] + 2dp[i - 1][1] + 2dp[i - 1][2] \\ dp[i][2] = dp[i - 1][1] + 2dp[i - 1][2] \end{matrix}
我一看，人群裆中……不对，这个好像可以用矩阵来表示转移。表示出来是下面这个样子
\begin{pmatrix} dp[i][0] \\ dp[i][1] \\ dp[i][2] \end{pmatrix} = \begin{pmatrix} dp[i-1][0] \\ dp[i-1][1] \\ dp[i-1][2] \end{pmatrix} \times \begin{pmatrix} 2 & 1 & 0 \\ 2 & 2 & 2 \\ 0 & 1 & 2 \end{pmatrix}
那显然这个可以矩阵快速幂算一下，把后面那个转移矩阵n次方一下就好了。

代码

// Code by KSkun, 2018/3
#include <cstdio>
#include <cstring>

typedef long long LL;

inline char fgc() {
    static char buf[100000], *p1 = buf, *p2 = buf;
    return p1 == p2 && (p2 = (p1 = buf) + fread(buf, 1, 100000, stdin), p1 == p2) ? EOF : *p1++;
}

inline int readint() {
    register int res = 0, neg = 1;
    char c = fgc();
    while(c < '0' || c > '9') {
        if(c == '-') neg = -1;
        c = fgc();
    }
    while(c >= '0' && c <= '9') {
        res = res * 10 + c - '0';
        c = fgc();
    }
    return res * neg;
}

const int MO = 10007;

struct Matrix {
    int m[3][3];
};

inline void mul(Matrix &a, Matrix b) {
    Matrix res;
    memset(res.m, 0, sizeof(res.m));
    for(int i = 0; i < 3; i++) {
        for(int j = 0; j < 3; j++) {
            for(int k = 0; k < 3; k++) {
                res.m[i][j] += a.m[i][k] * b.m[k][j];
                res.m[i][j] %= MO;
            }
        }
    }
    a = res;
}

inline Matrix fpow(Matrix x, int k) {
    if(k == 1) return x;
    Matrix res = fpow(x, k >> 1);
    mul(res, res);
    if(k & 1) {
        mul(res, x);
    }
    return res;
}

int T, n;
Matrix mat, def;

inline void init() {
    memset(mat.m, 0, sizeof(mat.m));
    mat.m[0][0] = 2;
    mat.m[0][1] = 1;
    mat.m[1][0] = mat.m[1][1] = mat.m[1][2] = 2;
    mat.m[2][1] = 1;
    mat.m[2][2] = 2;
    memset(def.m, 0, sizeof(def.m));
    def.m[0][0] = def.m[1][1] = def.m[2][2] = 1;
}

int main() {
    T = readint();
    while(T--) {
        n = readint();
        init();
        mat = fpow(mat, n);
        mul(def, mat);
        printf("%d\n", def.m[0][0]);
    }
    return 0;
}