写在前面：
-
上一次我们了解了矩阵快速幂，那么矩阵快速幂的应用场景有哪些？
-
最直接的应用，毫无疑问，只要有线性递推式，就可以使用矩阵快速幂优化计算
-
DP中的状态转移方程很多都是线性递推，我们可以用矩阵快速幂优化DP
题目描述：
衣食无忧的 Q老师 有一天突发奇想，想要去感受一下劳动人民的艰苦生活。
具体工作是这样的，有 N 块砖排成一排染色，每一块砖需要涂上红、蓝、绿、黄这 4 种颜色中的其中 1 种。且当这 N 块砖中红色和绿色的块数均为偶数时，染色效果最佳。
为了使工作效率更高，Q老师 想要知道一共有多少种方案可以使染色效果最佳，你能帮帮他吗？
思路：
定义状态：考虑用A[i] 表示 i 个格子，红绿均为偶数的染色方案数；B[i] 表示 i 个格子，红绿均为奇数的染色方案数；C[i] 表示 i 个格子，红绿有一个为偶数的染色方案数（其实A[i] B[i] C[i]就是F[i][0]，F[i][1]，F[i][2]，不过是换了个名字）
状态转移：A[i] = 2 * A[i-1] + C[i-1] ；B[i] = 2 * B[i-1] + C[i-1] ；C[i] = 2 * A[i-1] + 2 * B[i-1] + 2 * C[i-1] ，其中每一个状态转移都能用矩阵运算优化
边界条件：A[0]=1（红绿都是0个，0是偶数）；B[0]=C[0]=0
代码：
采用了静态建立矩阵的方式，使用了memcpy，代码比较简洁，可作为模板
#include <cstdio>
#include <iostream>
#include <cstring>
using namespace std;
long long K, MOD=10007;
const int N = 3;
struct Matrix
{
long long x[N + 1][N + 1];
Matrix operator*(const Matrix& y) const
{
Matrix ret; //ret==return
for (int i = 1; i <= N; ++i)
for (int j = 1; j <= N; ++j)
{
ret.x[i][j] = 0;
for (int k = 1; k <= N; ++k)
ret.x[i][j] = (ret.x[i][j] + (x[i][k] % MOD) * (y.x[k][j] % MOD) % MOD) % MOD;
}
return ret;
}
Matrix() { memset(x, 0, sizeof(x)); }
Matrix(const Matrix& t) { memcpy(x, t.x, sizeof(x)); }
};
Matrix mqpow(Matrix a, int x)
{
Matrix ret;
//置为单位矩阵
for (int i = 1; i <= N; i++)
ret.x[i][i] = 1;
//迭代矩阵快速幂
while (x)
{
if (x & 1) ret = ret * a;
a = a * a;
x >>= 1;
}
return ret;
}
int main()
{
int T; cin >> T;
while (T--)
{
long long M;
cin >> M;
Matrix A;
A.x[1][1] = 2; A.x[1][2] = 0; A.x[1][3] = 1;
A.x[2][1] = 0; A.x[2][2] = 2; A.x[2][3] = 1;
A.x[3][1] = 2; A.x[3][2] = 2; A.x[3][3] = 2;
Matrix halfAns = mqpow(A, M);
cout << halfAns.x[1][1] << endl;
}
return 0;
}