题目链接：http://codeforces.com/gym/101061/problem/B 题意：我们开始时有红绿蓝三种颜色花各一朵，每种下一朵红花，第二天会收获一朵红花、两朵绿花、三朵蓝花，每种下一朵蓝花，第二天会收获四朵红花、五朵绿花、六朵蓝花，每种下一朵绿花，第二天会收获七朵红花、八朵绿花、九朵蓝花。每天我们会种下所有花，求第n天时有多少花。其中， 1≤n≤109 。
想法：由于n高达 109 ，所以O(n)的做法肯定时不行的。那么O( log(n) )的做法就呼之欲出了：矩阵快速幂。我们先考虑 1∗3 的矩阵 Mi=[ri,gi,bi] ，代表各花的数量。然后会存在矩阵A，使得 Mi∗A=Mi+1 ，再向前递推，则有 Mn=An−1∗M1 ，根据给定的关系，矩阵A也很好确定， 就是
⎡⎣⎢⎢147258369⎤⎦⎥⎥
那么再加上快速幂即可，复杂度 O(logn) 。
代码如下：
#include <cstdio> #include <cstring> typedef long long ll; const int MOD = 1000000007; struct mat{ ll a[3][3]; void init(){ memset(a, 0, sizeof(a)); a[0][0] = a[1][1] = a[2][2] = 1; } mat operator *(const mat &b){ mat t; t.init(); for(int i = 0; i < 3; ++i){ for(int j = 0; j < 3; ++j){ t.a[i][j] = 0; for(int k = 0; k < 3; ++k){ t.a[i][j] = (t.a[i][j] + a[i][k] * b.a[k][j]) % MOD; } } } return t; } }; mat powmod(mat x, int b){ mat r; r.init(); while(b){ if(b & 1){ r = r * x; } x = x * x; b >>= 1; } return r; } int main(){ int cas; scanf("%d", &cas); while(cas--){ int n; scanf("%d", &n); mat x; x.a[0][0] = 1; x.a[0][1] = 2; x.a[0][2] = 3; x.a[1][0] = 4, x.a[1][1] = 5; x.a[1][2] = 6; x.a[2][0] = 7; x.a[2][1] = 8; x.a[2][2] = 9; x = powmod(x, n - 1); ll ans = 0; for(int i = 0; i < 3; ++i){ for(int j = 0; j < 3; ++j){ ans = (ans + x.a[i][j]) % MOD; } } printf("%I64d\n", ans); } return 0; }