[POJ3734]Blocks（递推，矩阵快速幂）

题目链接：http://poj.org/problem?id=3734

题意：n个方块4个颜色，现在要求涂色，其中两种颜色的数量是偶数，问多少种情况。

考虑sta(i)为当前i块的时候的合法涂色种类数，则有：EE、OE(EO)、OO三种情况。

EEi = 2 * EE(i-1) + OE(EO)(i-1)

OOi = OE(EO)i + 2 * OO(i-1)

OE(EO)i = 2 * (OO(i-1) + OE(EO)(i-1) + EE(i-1))

抽取出系数，矩阵为

|2 1 0|

|0 1 2|

|2 2 2|

最终合法为EEn，则是第一行第一列。

 1 #include <algorithm>
 2 #include <iostream>
 3 #include <iomanip>
 4 #include <cstring>
 5 #include <climits>
 6 #include <complex>
 7 #include <cassert>
 8 #include <cstdio>
 9 #include <bitset>
10 #include <vector>
11 #include <deque>
12 #include <queue>
13 #include <stack>
14 #include <ctime>
15 #include <set>
16 #include <map>
17 #include <cmath>
18 using namespace std;
19 
20 typedef long long LL;
21 
22 const int mod = 10007;
23 const int maxn = 100;
24 typedef struct Matrix {
25     int m[maxn][maxn];
26     int r;
27     int c;
28     Matrix() {
29         r = c = 0;
30         memset(m, 0, sizeof(m));
31     }
32 } Matrix;
33 
34 Matrix mul(Matrix m1, Matrix m2, int mod) {
35     Matrix ans = Matrix();
36     ans.r = m1.r;
37     ans.c = m2.c;
38     for(int i = 1; i <= m1.r; i++) {
39         for(int j = 1; j <= m2.r; j++) {
40             for(int k = 1; k <= m2.c; k++) {
41                 if(m2.m[j][k] == 0) continue;
42                 ans.m[i][k] = ((ans.m[i][k] + m1.m[i][j] * m2.m[j][k] % mod) % mod) % mod;
43             }
44         }
45     }
46     return ans;
47 }
48 
49 Matrix quickmul(Matrix m, int n, int mod) {
50     Matrix ans = Matrix();
51     for(int i = 1; i <= m.r; i++) ans.m[i][i]  = 1;
52     ans.r = m.r;
53     ans.c = m.c;
54     while(n) {
55         if(n & 1) ans = mul(m, ans, mod);
56         m = mul(m, m, mod);
57         n >>= 1;
58     }
59     return ans;
60 }
61 
62 int n;
63 
64 int main() {
65 //    freopen("in", "r", stdin);
66     int T;
67     scanf("%d", &T);
68     while(T--) {
69         scanf("%d", &n);
70         Matrix A;
71         A.r = A.c = 3;
72         A.m[1][1] = 2; A.m[1][2] = 1; A.m[1][3] = 0;
73         A.m[2][1] = 2; A.m[2][2] = 2; A.m[2][3] = 2;
74         A.m[3][1] = 0; A.m[3][2] = 1; A.m[3][3] = 2;
75         Matrix B = quickmul(A, n, mod);
76         printf("%d
", B.m[1][1]);
77     }
78     return 0;
79 }