矩阵类题目专题

本文从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("");
}
}
};