Q老师染砖（矩阵快速幂优化DP）

83 阅读 0 评论 55 点赞

我是靠谱客的博主畅快指甲油，这篇文章主要介绍Q老师染砖（矩阵快速幂优化DP），现在分享给大家，希望可以做个参考。

问题描述

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

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

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

Input

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

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

Output

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

Sample input

复制代码

Sample output

复制代码

解题思路

首先我们可以发现这个题有很明显的子结构特性，因此可以使用DP来做，但是n的数据范围十分大。我们考虑应该用什么优化。

设 $A [i]$ 为 $i$ 个格子，红绿均为偶数的方案数，但是这个状态不够，因为当前状态除了红绿均为偶数还有其他情况，我们还要添加两个状态。

设 $B [i]$ 为 $i$ 个格子，红绿均为奇数的方案数， $C [i]$ 为 $i$ 个格子，红绿只有一个是偶数的方案数。

我们可以列出线性转移方程：
$C[i-1]\ B[i] = 2 times B[i-1] + C[i-1]\ C[i]=2*A[i-1]+2times B[i-1]+2times C[i-1] end{cases}$
由于这是线性转移方程，我们很容易想到矩阵快速幂优化，作出转移矩阵如下：
$A[i]\ B[i]\ C[i] end{bmatrix} =begin{bmatrix} 2&0&1\ 0&2&1\ 2&2&2\ end{bmatrix} *ans[i-1]$
因此可以使用矩阵快速幂优化DP来做这道题，初始状态 $A [1] = 2, B [1] = 0, C [1] = 2$ 。

完整代码

复制代码

#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <climits>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

struct Matrix{
    Matrix(int _size=0) {
        Size=_size; mat=new int*[Size];
        for (int i=0; i<Size; i++) mat[i]=new int[Size];
        for (int i=0; i<Size; i++)
            for (int j=0; j<Size; j++)
                mat[i][j]=0;
    }
    Matrix(const Matrix& t){
        Size=t.Size; mat=new int*[Size];
        for (int i=0; i<Size; i++) mat[i]=new int[Size];
        memcpy(mat,t.mat,sizeof(mat));
    }
    ~Matrix(){
        for (int i=0; i<Size; i++) delete[] mat[i];
        delete[] mat;
    }
    Matrix operator*(const Matrix& t) const{
        Matrix ret(Size);
        for (int i=0; i<Size; ++i)
            for (int j=0; j<Size; ++j)
                for (int k=0; k<Size; ++k)
                    ret.mat[i][j]+=mat[i][k]*t.mat[k][j];
        return ret;
    }
    Matrix operator%(const int m) const {
        Matrix ret(Size);
        for (int i=0; i<Size; i++)
            for (int j=0; j<Size; j++)
                ret.mat[i][j]=mat[i][j]%m;
        return ret;
    }
    Matrix& operator=(const Matrix& t){
        for (int i=0; i<Size; i++) delete[] mat[i];
        delete[] mat;
        Size=t.Size;
        mat=new int*[Size];
        for (int i=0; i<Size; i++) mat[i]=new int[Size];
        for (int i=0; i<Size; i++)
            for (int j=0; j<Size; j++)
                mat[i][j]=t.mat[i][j];
        return *this;
    }
    void quick_pow(int x,int m){//x次幂模m
        Matrix ret(Size);
        for (int i=0; i<Size; i++) ret.mat[i][i]=1;
        while(x){
            if(x&1) {
                ret=ret*(*this); ret=ret%m;
            }
            *this=(*this)*(*this);
            *this=(*this)%m;
            x>>=1;
        }
        *this=ret;
    }
    void output(){
        printf("Size: %dn",Size);
        for (int i=0; i<Size; i++){
            for (int j=0; j<Size; j++)
                printf("%d ",mat[i][j]);
            printf("n");
        }
    }
    int Size;
    int** mat;
};
int getint(){
    int x=0,s=1; char ch=' ';
    while(ch<'0' || ch>'9'){ ch=getchar(); if(ch=='-') s=-1;}
    while(ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar();}
    return x*s;
}
int t,n;
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    t=getint();
    while(t--){
        n=getint();
        Matrix mat1(3);
        mat1.mat[0][0]=2; mat1.mat[0][1]=0; mat1.mat[0][2]=1;
        mat1.mat[1][0]=0; mat1.mat[1][1]=2; mat1.mat[1][2]=1;
        mat1.mat[2][0]=2; mat1.mat[2][1]=2; mat1.mat[2][2]=2;
        mat1.quick_pow(n-1,10007);
        //mat1.output();
        long long ans=0;
        ans=mat1.mat[0][0]*2+mat1.mat[0][2]*2; ans%=10007;
        printf("%lldn",ans);
    }
    return 0;
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <climits>
#include <algorithm>
#include <queue>
#include <vector>
using namespace std;

struct Matrix{
    Matrix(int _size=0) {
        Size=_size; mat=new int*[Size];
        for (int i=0; i<Size; i++) mat[i]=new int[Size];
        for (int i=0; i<Size; i++)
            for (int j=0; j<Size; j++)
                mat[i][j]=0;
    }
    Matrix(const Matrix& t){
        Size=t.Size; mat=new int*[Size];
        for (int i=0; i<Size; i++) mat[i]=new int[Size];
        memcpy(mat,t.mat,sizeof(mat));
    }
    ~Matrix(){
        for (int i=0; i<Size; i++) delete[] mat[i];
        delete[] mat;
    }
    Matrix operator*(const Matrix& t) const{
        Matrix ret(Size);
        for (int i=0; i<Size; ++i)
            for (int j=0; j<Size; ++j)
                for (int k=0; k<Size; ++k)
                    ret.mat[i][j]+=mat[i][k]*t.mat[k][j];
        return ret;
    }
    Matrix operator%(const int m) const {
        Matrix ret(Size);
        for (int i=0; i<Size; i++)
            for (int j=0; j<Size; j++)
                ret.mat[i][j]=mat[i][j]%m;
        return ret;
    }
    Matrix& operator=(const Matrix& t){
        for (int i=0; i<Size; i++) delete[] mat[i];
        delete[] mat;
        Size=t.Size;
        mat=new int*[Size];
        for (int i=0; i<Size; i++) mat[i]=new int[Size];
        for (int i=0; i<Size; i++)
            for (int j=0; j<Size; j++)
                mat[i][j]=t.mat[i][j];
        return *this;
    }
    void quick_pow(int x,int m){//x次幂模m
        Matrix ret(Size);
        for (int i=0; i<Size; i++) ret.mat[i][i]=1;
        while(x){
            if(x&1) {
                ret=ret*(*this); ret=ret%m;
            }
            *this=(*this)*(*this);
            *this=(*this)%m;
            x>>=1;
        }
        *this=ret;
    }
    void output(){
        printf("Size: %dn",Size);
        for (int i=0; i<Size; i++){
            for (int j=0; j<Size; j++)
                printf("%d ",mat[i][j]);
            printf("n");
        }
    }
    int Size;
    int** mat;
};
int getint(){
    int x=0,s=1; char ch=' ';
    while(ch<'0' || ch>'9'){ ch=getchar(); if(ch=='-') s=-1;}
    while(ch>='0' && ch<='9'){ x=x*10+ch-'0'; ch=getchar();}
    return x*s;
}
int t,n;
int main(){
    //ios::sync_with_stdio(false);
    //cin.tie(0);
    t=getint();
    while(t--){
        n=getint();
        Matrix mat1(3);
        mat1.mat[0][0]=2; mat1.mat[0][1]=0; mat1.mat[0][2]=1;
        mat1.mat[1][0]=0; mat1.mat[1][1]=2; mat1.mat[1][2]=1;
        mat1.mat[2][0]=2; mat1.mat[2][1]=2; mat1.mat[2][2]=2;
        mat1.quick_pow(n-1,10007);
        //mat1.output();
        long long ans=0;
        ans=mat1.mat[0][0]*2+mat1.mat[0][2]*2; ans%=10007;
        printf("%lldn",ans);
    }
    return 0;
}