题目的大意:

给定待粉刷的n个墙砖(排成一行)，每个墙砖可以粉刷的颜色种类为:红、蓝、绿、黄，

问粉刷完毕后，红色墙砖和蓝色墙砖都是偶数的粉刷方式有多少种(结果对10007取余).

解题思路:

思路用的是递推.假设粉刷到第i个墙砖时，使用的红色墙砖和蓝色墙砖都是偶数的方案

数有ai，使用的红色和蓝色墙砖一奇一偶的方案数为bi，使用的红色和蓝色墙砖都是奇数的

方案数为ci，那么，我们容易得到下面的递推式:

看到上式，对于学过线代的人来说一定不陌生，我们可以将其写成矩阵的形式，然后会发现该

<??http://www.2cto.com/kf/ware/vc/" target="_blank" class="keylink">vcD4KPHA+td3Nxsq9yse1yLHIyv3B0LXE0M7KvS48L3A+CjxwPjxicj4KPC9wPgo8cD48aW1nIHNyYz0="https://www.cppentry.com/upload_files/article/49/1_ubspq__.jpg" alt="\">

对于求取ai，我们可通过计算相应矩阵的幂得知，计算矩阵的幂，利用快速二分幂，

可将时间复杂度降为O(lgn).

解题代码:

#include
  
   
#include
   
     #include
    
      #define M 10007 using namespace std; //矩阵乘法 vector
     
       > multi(vector
      
        > &A, vector
       
         > &B) { vector
        
          > C(A.size(), vector
         
          (B[0].size())); for (unsigned i = 0; i != A.size(); ++i) for (unsigned j = 0; j != B[0].size(); ++j) for (unsigned k = 0; k != B.size(); ++k) C[i][j] = (C[i][j] + A[i][k] * B[k][j]) % M; return C; } //二分快速幂 vector
          
            > power(vector
           
             > &A, int n) { vector
            
              > B(A.size(), vector
             
              (A.size())); for (int i = 0; i != A.size(); ++i) B[i][i] = 1; while (n) { if (n & 1) B = multi(B, A); A = multi(A, A), n >>= 1; } return B; } int main() { int t,n; cin >> t; while (t--) { vector
              
                > A(3, vector
               
                (3)); A[0][0] = 2, A[0][1] = 1, A[0][2] = 0; A[1][0] = 2, A[1][1] = 2, A[1][2] = 2; A[2][0] = 0, A[2][1] = 1, A[2][2] = 2; cin >> n; A = power(A, n); cout << A[0][0] << endl; } return 0; }