【学习笔记】矩阵 Matrix

发表于 更新于

矩阵的运算法则

$ \huge + $ 加法，两个行数和列数分别相同的矩阵可以进行加法运算，Ans矩阵每个位置上的数为两个矩阵相应位置上的数的和
$ \huge - $ 减法，与加法类似两个行数和列数分别相同的矩阵可以进行减法运算，Ans矩阵每个位置上的数为两个矩阵相应位置上的数的差
$ \huge $ 数乘，表现为一个数乘一个矩阵，具体效果就是矩阵的每个位置上的数都乘上需要数乘的数。
以上三种运算都比较简单，直接可以理解。接下来讲一个复杂的东西。
$ \huge\times $ 叉乘，一个矩阵乘上另一个矩阵，只有在前面的矩阵的行数等于第二个矩阵的列数时可以进行运算（可以看出来，矩阵的叉乘不满足交换律），先写一下矩阵叉乘的定义：
假设$A \times B = C，A，B，C$均为矩阵。
$ C{i, j} = \sum{k=1}^{len}A_{i, k} B_{k, j}$
$ len$ 是A的行数或B的列数。
这里写图片描述
上面的这个图中的$C$矩阵是33的，图中只画出了一个。
$58 = 1 7 + 2 9 + 3 11$,这下应该解释清楚了。
因为矩阵乘法满足交换律，所以对矩阵乘方可以用快速幂加速。

$\text{Code}$

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
typedef long long ll;
struct Matrix {  
 	int row, col, limit;
	std::vector< std::vector< ll > > num;
  	Matrix() {
  		row = col = 0;
  		limit = 0x3f3f3f3f;
  		num.clear();
	}
	Matrix(int _row, int _col, int _limit) {
		this->row = _row;
		this->col = _col;
		this->limit = _limit;
		num.clear();
		num.resize(row + 1);
		for (int i = 1; i <= row; i++)
			num[i].resize(col + 1);
	}
	Matrix(int _row, int _col, int _limit, long long *list) {
		this->row = _row;
		this->col = _col;
		this->limit = _limit;
		num.clear();
		num.resize(row + 1);
		for (int i = 1; i <= _row; i++) {
			num[i].resize(col + 1);
			for (int j = 1; j <= _col; j++) 
				num[i][j] = list[(i - 1) * _row + j];
		}
	}
    Matrix operator + (const Matrix& rhs) {
    	assert(this->row == rhs.row && this->col == rhs.col);
    	for (int i = 1; i <= row; i++)
    		for (int j = 1; j <= col; j++) 
    			this->num[i][j] += rhs.num[i][j],
    			this->num[i][j] %= limit;
    	return *this;
	}
	Matrix operator - (const Matrix& rhs) {
    	assert(this->row == rhs.row && this->col == rhs.col);
    	for (int i = 1; i <= row; i++)
    		for (int j = 1; j <= col; j++) 
    			this->num[i][j] -= rhs.num[i][j],
    			this->num[i][j] %= limit;
    	return *this;
	}
	Matrix operator * (const long long& rhs) {
		for (int i = 1; i <= this->row; i++) 
			for (int j = 1; j <= this->col; j++)
				this->num[i][j] *= rhs,
				this->num[i][j] %= this->limit;
	}
	Matrix operator * (const Matrix& rhs) {
		assert(this->col == rhs.row);
		Matrix ans = Matrix(this->row, col, this->limit);
		for (int i = 1; i <= this->row; i++) 
			for (int j = 1; j <= rhs.col; j++)
				for (int k = 1; k <= this->col; k++) 
					ans.num[i][j] += this->num[i][k] * rhs.num[k][j],
					ans.num[i][j] %= this->limit;
		return ans;
	}
	Matrix operator ^ (ll p) {
		assert(this->row == this->col);
		Matrix ans = Matrix(this->row, this->col, this->limit);
		for (int i = 1; i <= this->row; i++) 
			ans.num[i][i] = 1;
		while (p) {
			if (p & 1) ans = ans * *this;
			*this = *this * *this;
			p >>= 1;
		}
		return ans;
	}
};

写了若干个构造函数，含义应该也很明显了，
矩阵快速幂嘛，，，整数快速幂里面拿过来的啦~~~，修改一下就OK了。
虽说重载^纯属个人喜好。。。