[week14] D - Q老师染砖（选做） —— 矩阵快速幂优化DP

题意

衣食无忧的 Q老师 有一天突发奇想，想要去感受一下劳动人民的艰苦生活。

具体工作是这样的，有 N 块砖排成一排染色，每一块砖需要涂上红、蓝、绿、黄这 4 种颜色中的其中 1 种。且当这 N 块砖中红色和绿色的块数均为偶数时，染色效果最佳。

为了使工作效率更高，Q老师 想要知道一共有多少种方案可以使染色效果最佳，你能帮帮他吗？

Input

第一行为 T，代表数据组数。(1 ≤ T ≤ 100)

接下来 T 行每行包括一个数字 N，代表有 N 块砖。(1 ≤ N ≤ 1e9)

Output

输出满足条件的方案数，答案模 10007。

输入样例

2
1
2

输出样例

2
6

提示

分析

这是一道用矩阵快速幂优化DP解决的问题。

• 矩阵快速幂优化DP

1. 什么是矩阵快速幂优化DP？

回顾一下矩阵快速幂👉[week14] Q老师的考验——矩阵快速幂

在动态规划过程当中，利用矩阵快速幂对动态规划求解进行优化就是矩阵快速幂优化DP。

若列出的状态转移方程符合矩阵快速幂转换条件，则可以使用矩阵快速幂对动态求解进行优化。一般这样的动态规划题目中的状态涉及多个方程。

2. 经典题型

• 染砖问题
  

（1）定状态

易发现，可以利用A[i]表示答案

但是在染砖过程中，涉及到的状态不止是A[i]所代表的状态，还有两种情况。即红绿砖数量均为偶数的情况需要由红绿均为奇数和红绿中有一个为偶数转换而得。

（2）状态转移方程

根据题意可知，对于每一块砖有四种颜色的选项，其中只有红绿要求是全为偶数：

⚠️注意：数量为0同样视作是数量为偶数。

• A[i]：
  • 若前i - 1块砖满足红绿都为偶数，则第 i 块砖颜色为蓝和黄时，i 块砖中的红绿砖数仍然都为偶数，则A[i] = A[i - 1] * 2
  • 若前i - 1块砖满足红绿其中一种为偶数，则第i块砖颜色为红或绿时（哪一个颜色为奇数选择哪一个），i块砖满足红绿砖数都为偶数，则A[i] = C[i - 1]
• B[i]：
  • 若前i - 1块砖满足红绿都为奇数，则第 i 块砖颜色为蓝和黄时，i 块砖中的红绿砖数仍然都为奇数，则B[i] = B[i - 1] * 2
  • 若前i - 1块砖满足红绿其中一个为奇数，则第 i 块砖颜色为红或绿时（哪一个为偶数选择哪一个），i 块砖中的红绿砖数都为奇数，则B[i] = C[i - 1]
• C[i]：
  • 若前i - 1块砖满足红绿都为奇数，则第 i 块砖颜色为红和绿时，i 块砖中的红绿砖数有一个为偶数，则C[i] = A[i - 1] * 2
  • 若前i - 1块砖满足红绿其中一个为奇数，则第 i 块砖颜色为蓝和黄时，i 块砖中的红绿砖数其中一个为奇数，则C[i] = C[i - 1] * 2
  • 若前i - 1块砖满足红绿都为奇数，则第 i 块砖颜色为蓝和黄时，i 块砖中的红绿砖数都为奇数，则C[i] = B[i - 1] * 2

（3）方程转换

根据矩阵快速幂的特征，该方程可以转化为：

累乘矩阵^（i - 1） 结果矩阵（令i = 1）*

累乘矩阵即为上图等式中与ans[i - 1]相乘的数字矩阵
结果矩阵即为上图等式中等于ans[i]的变量矩阵

令i = 1时，即代表只有一块砖的情况，则：
A[1] = 2
B[1] = 0
C[1] = 2

最后与i = 1的结果矩阵中相乘是因为ans[i]根据矩阵快速幂拆分后等于：

ans[i] = 累乘矩阵 * 累乘矩阵 * … * ans[1]

最终，ans[i] = A[i]

• 题目分析

这道题就是典型的染砖问题，根据上述分析实现代码即可。

染砖问题在代码中，需要手动将累乘的数字矩阵输入创建，并且在得到累乘结果后，将累乘结果矩阵中的第一行与ans[1]相乘得到结果。

将ans[i]转换为矩阵快速幂进行求解是为了优化计算过程。但ans[i]等于A[i]，其他两个状态是转移到A[i]过程中出现的其他状态。

总结

1. 矩阵快速幂还挺好用的，但难点仍然在于DP分析，列出状态和方程。

代码

//
//  main.cpp
//  lab4
//
//

#include <iostream>
using namespace std;

const int n = 3;
long long p = 10007;        //模

struct Matrix           //累乘矩阵结构体
{
    long long x[n][n];      //矩阵
    
    Matrix operator*(const Matrix & t) const        //重载矩阵乘法
    {
        Matrix ans;
        for( int i = 0 ; i < n ; i++ )
            for( int j = 0 ; j < n ; j++ )
            {
                ans.x[i][j] = 0;
                
                for( int k = 0 ; k < n ; k++ )
                {
                    ans.x[i][j] += x[i][k] * t.x[k][j] % p;
                    ans.x[i][j] %= p;       //每个所得数都要模p，否则当累乘次数过大时会wa
                }
                
            }
        return ans;
    }
    
   //初始化和复制构造函数
    Matrix(){ memset(x, 0, sizeof(x)); }
    Matrix(const Matrix &t){memcpy(x, t.x, sizeof(x)); }
    
};

Matrix quick_pow(Matrix t,long long num)        //快速幂
{
   Matrix ans;
   
   memset(ans.x, 0, sizeof(ans.x));
   
   for( int i = 0 ; i < n ; i++ )       //累乘的基本单位为单位矩阵
       ans.x[i][i] = 1;                 //除对角线上全为1外，其余都为0
   
   while (num)                  //累乘
   {
       if( num & 1 )
           ans = ans * t;
       
       t = t * t;
       
       num >>= 1;
       
   }
   
   return ans;
}
   

int main()
{
    ios::sync_with_stdio(false);
    
    int t = 0,num = 0;
    cin>>t;
    
    while( t-- )
    {
        cin>>num;
        
        Matrix a;
        
        //累乘矩阵
        a.x[0][0] = 2;
        a.x[0][1] = 0;
        a.x[0][2] = 1;
        a.x[1][0] = 0;
        a.x[1][1] = 2;
        a.x[1][2] = 1;
        a.x[2][0] = 2;
        a.x[2][1] = 2;
        a.x[2][2] = 2;
        
        Matrix res = quick_pow(a, num - 1);     //累乘砖块数 - 1次
        
        cout<<(res.x[0][0] * 2 + res.x[0][2] * 2) % p<<endl;
        //再与只有1个砖块时的a[1]b[1]c[1]相乘，得到答案
       
        
    }
    
    return 0;
}