G-rated

What are you waiting for?

0%

矩阵类题目专题

本文从WordPress迁移而来, 查看全部WordPress迁移文章

目的其实是复习一下基础，矩阵类的题目，经常用到矩阵快速幂，当然矩阵快速幂本身不是很难。题目一般是数学类的题目，用矩阵来优化，另外，也有不少dp的题目用矩阵优化。通用地说，如果能得到线程方程，就有可能可以用矩阵来优化

模板

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
/*
矩阵里面，有一个元素是负数，这样做矩阵快速幂取模或乘法取模的时候，会让有些元素变为负数
所以每个取模的地方，都加上 + MOD
*/
#define MAXSIZE 3
#define MOD 1024
 
class matrix{

//为了方便操作，数据域为public
public:
    //定义矩阵类型，常用的是int,long long,double
    typedef int elemtype; 
    int row,col;         
    elemtype a[MAXSIZE][MAXSIZE];

public:
    matrix(){}
    matrix(int r,int c):row(r),col(c){}
    ~matrix(){}
   
    //重新设置行列
    void reset(int r,int c){ row = r; col = c; }
    //将矩阵设为0矩阵
    void zero(){ memset(a,0,sizeof(a)); }
    //将矩阵设为1矩阵
    void one(){ 
    for(int i = 0; i < row; i++) 
        for(int j = 0; j < col; j++) 
            a[i][j] = 1; 
    }
    //将矩阵设为单位矩阵
    void identity(){
        memset(a,0,sizeof(a));
        for(int i = 0; i < MAXSIZE; i++) a[i][i] = 1;
    }

    //重载 = + - * 运算符，其中 + - * 都是取模的
    //如果题目不需要取模，可以把 %MOD 去掉
    //或者把 MOD 设置得很大，因为不用取模，意味着运算结果不会太大
    void add_sub(const matrix &temp,matrix &now,bool isadd){
        elemtype flag = isadd ? 1 : -1;
        for(int i = 0; i < row; i++)
            for(int j = 0;  j < col; j++)
                now.a[i][j] = (a[i][j] + flag * temp.a[i][j] + MOD) % MOD;
    }

    //保证 A.row = B.row , A.col = B.col
    void operator = (const matrix &temp){
        row = temp.row; col = temp.col;
        for(int i = 0 ; i < row; i++)
            for(int j = 0; j < col; j++)
                a[i][j] = temp.a[i][j];
    }
   
    //保证 A.row = B.row , A.col = B.col
    matrix  operator + (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,true);
        return now;
    }

    //保证 A.row = B.row , A.col = B.col
    matrix  operator - (const matrix &temp){
        matrix now(row,col);
        add_sub(temp,now,false);
        return now;
    }

    //保证 A.col = B.row
    matrix  operator * (const matrix &temp){
        matrix now(row,col);
        now.zero();
        for(int i = 0; i < row; i++)
            for(int j = 0; j < col; j++)
                for(int k = 0; k < col; k++)
                    now.a[i][j] = (now.a[i][j] + a[i][k] * temp.a[k][j] + MOD) % MOD;
        return now;
    }
   
    // 快速幂，操作的结果是保存在now中，不改变自身
    matrix operator ^ (int m){
        matrix now(row,col);
        matrix temp = (*this);
        now.identity(); //设为单位矩阵
        while(m){
            if(m&1) now = now * temp;
            temp = temp * temp;
            m /= 2;
        }
        return now;
    }
    void show(){
        for(int i = 0 ; i < row; i++){
            for(int j = 0; j < col; j++)
                printf("%d ",a[i][j]);
            puts("");
        }
    }
};