矩阵乘法

前提条件：只有当第一个矩阵的列数与第二个矩阵的行数相同时，才能进行乘法运算
运算规则：矩阵 a $\times$ 矩阵 b = 矩阵 ans，$ans{ij} = \sum{k=1} a{ik} \times b{kj}$
题目链接

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
#include <bits/stdc++.h>
using namespace std;

const int N = 110, mod = 1e9 + 7;

struct node {
	int a[N][N], r, c;
	node () {memset(a, 0, sizeof a);}

	node operator * (const node &w) const {
		node res;
		for (int i = 1; i <= r; i++) {
			for (int j = 1; j <= w.c; j++) {
				for (int kk = 1; kk <= c; kk++) {
					res.a[i][j] += a[i][kk] * w.a[kk][j];
					// cout << a[i][kk] << " " << w.a[kk][j] << endl;
				}
			}
		}
		return res;
	}
};

signed main() {
	int n, m, k;
	cin >> n >> m >> k;

	node a, b;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) cin >> a.a[i][j];
	}
	a.r = n; a.c = m;

	for (int i = 1; i <= m; i++) {
		for (int j = 1; j <= k; j++) cin >> b.a[i][j];
	}
	b.r = m; b.c = k;

	node res = a * b;
	for (int i = 1; i <= n; i++, cout << endl) {
		for (int j = 1; j <= k; j++, cout << " ") {
			// for (int kk = 1; kk <= m; kk++) {
			// 	c[i][j] += a[i][kk] * b[kk][j];
			// } 
			cout << res.a[i][j];
		}
	}
}

矩阵快速幂

根据乘法的结合律，我们可知 $A^n = A^{n/2} \times A^{n/2}$
根据这个性质，对于求 $A^n$ 我们可以用快速幂以 $log(n)$ 的复杂度快速求出
具体实现可以参考数字的快速幂
题目链接

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
#include <bits/stdc++.h>
using namespace std;

#define int long long
const int N = 110, mod = 1e9 + 7;

struct Matrix {
    int a[N][N]{}, n, m;

    Matrix() {}

    Matrix(int _n, int _m) {
        n = _n; m = _m;
    }
    
    Matrix(int _n) {
        n = _n; m = _n;
        for (int i = 1; i <= n; i++) a[i][i] = 1;
    }

    Matrix operator+(const Matrix &w) const {
        Matrix res(n, m);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= m; j++) {
                res.a[i][j] = a[i][j] + w.a[i][j];
            }
        }
        return res;
    }

    Matrix operator*(const Matrix &w) const {
        Matrix res(n, w.m);
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= w.m; j++) {
                for (int k = 1; k <= m; k++) {
                    (res.a[i][j] += a[i][k] * w.a[k][j] % mod) %= mod;
                }
            }
        }
        return res;
    }
};

int qmi(int a, int b) {
    int res = 1;
    while(b) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

Matrix qmi(Matrix a, int b) {
    Matrix res(a.n); // 
    while(b) {
        if (b & 1) res = res * a; 
        a = a * a;
        b >>= 1;
    }
    return res;
}

signed main() {
    int n, m;
    cin >> n >> m;

    Matrix a(n, n);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cin >> a.a[i][j];
        }
    }

    Matrix res = qmi(a, m);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++) {
            cout << res.a[i][j] << " ";
        }
        cout << endl;
    }    
}

矩阵快速幂加速递推

根据递推式子，构造矩阵，使用矩阵快速幂加速
题目链接

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
#include <bits/stdc++.h>

using namespace std;

#define int long long

const int N = 10, mod = 1e9 + 7;

struct Matrix{
    int a[N][N]{}, n, m;
    Matrix operator* (const Matrix &w) const{
        Matrix res;
        res.n = n;
        res.m = w.m;
        for (int i = 1; i <= n; i++) {
            for (int j = 1; j <= w.m; j++) {
                for (int k = 1; k <= m; k++) {
                    res.a[i][j] += a[i][k] * w.a[k][j] % mod;
                    res.a[i][j] %= mod;
                }
            }
        }
        return res;
    }
};

Matrix qmi(Matrix a, int b) {
    Matrix res;
    res.n = 3; res.m = 3;
    res.a[1][1] = 1; res.a[1][2] = 0; res.a[1][3] = 0;
    res.a[2][1] = 0; res.a[2][2] = 1; res.a[2][3] = 0;
    res.a[3][1] = 0; res.a[3][2] = 0; res.a[3][3] = 1;

    while(b) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}

signed main() {
    Matrix a, b;
    a.n = 1; a.m = 3;
    a.a[1][1] = 1; a.a[1][2] = 1; a.a[1][3] = 1;

    b.n = 3; b.m = 3;
    b.a[1][1] = 0; b.a[1][2] = 0; b.a[1][3] = 1;
    b.a[2][1] = 1; b.a[2][2] = 0; b.a[2][3] = 0;
    b.a[3][1] = 0; b.a[3][2] = 1; b.a[3][3] = 1;

    int T;
    cin >> T;
    while(T--) {
        int n;
        cin >> n;
        cout << (a * qmi(b, n - 1)).a[1][1] << endl;
    }
}

高斯消元

求解多元一次方程组的解
题目链接

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
#include <bits/stdc++.h>
using namespace std;

const int N = 110;
const double eps = 1e-9;
double a[N][N], ans[N];

signed main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n + 1; j++) {
            cin >> a[i][j];
        }
    }

    int r = 1;
    for (int c = 1; c <= n; c++) {
        int t = r;
        for (int i = r; i <= n; i++) {
            if (fabs(a[i][c]) > fabs(a[t][c])) t = i;
        }
        if (fabs(a[t][c]) <= eps) continue;
        swap(a[t], a[r]);

        for (int i = r + 1; i <= n; i++) {
            double p = a[i][c] / a[r][c];
            for (int j = c; j <= n + 1; j++) {
                a[i][j] -= a[r][j] * p;
            }
        }
        r++;
    }

    if (r <= n) {
        for (int i = r; i <= n; i ++) {
            if (fabs(a[i][n + 1]) > eps) {
                cout << -1 << endl;
                return 0;
            }
        }
        cout << 0 << endl;
        return 0;
    }
    for (int i = n; i >= 1; i--) {
        a[i][n + 1] /= a[i][i];
        for (int j = 1; j < i; j++) {
            a[j][n + 1] -= a[j][i] * a[i][n + 1];
        }
    }

    for (int i = 1; i <= n; i++) {
        cout << "x" << i << "=" << fixed << setprecision(2) << a[i][n + 1] << endl;
    }
}

矩阵求逆

概念： 类似于一个数的逆元。只有方阵才有逆矩阵，一个方阵 $A$ 的逆是 $A^{-1}$，那么有如下几个性质：
$A \times A^{-1} = I$
$B \times A^{-1} = C \Rightarrow C \times A = B$
算法原理：
$ A^{-1} \times [AI] = [IA^{-1}] $
所以我们只需要将 $[AI]$ 的左边转成$[I]$那么右边的就是 $[A^{-1}]$
题目链接

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
#include <bits/stdc++.h>
using namespace std;
 
#define int long long
const int N = 410, mod = 1e9 + 7;
int a[N][N * 2];

int qmi(int a, int b) {
    int res = 1;
    while(b) {
        if (b & 1) res = res * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return res;
}

signed main() {
    int n;
    cin >> n;

    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= n; j++)
            cin >> a[i][j];
        a[i][i + n] = 1;
    }

    int r = 1;
    for (int c = 1; c <= n; c++) {
        if (!a[r][r])
        for (int i = r + 1; i <= n; i++) {
            if (a[i][r]) {
                swap(a[r], a[i]);
                break;
            }
        }
        if (a[r][r] == 0) {
            cout << "No Solution" << endl;
            return 0;
        }

        int p = qmi(a[r][r], mod - 2);
        for (int i = r; i <= n + n; i++) {
            a[r][i] *= p;
            a[r][i] %= mod;
        }

        for (int i = r + 1; i <= n; i++) {
            for (int j = n + n; j >= r; j--) {
                a[i][j] -= a[r][j] * a[i][r] % mod;
                a[i][j] += mod;
                a[i][j] %= mod;
            }
        }
        r++;
    }

    for (int i = n; i >= 1; i--) {
        for (int j = i - 1; j >= 1; j--) {
            for (int k = n + n; k >= i; k--) {
                a[j][k] -= a[i][k] * a[j][i] % mod;
                a[j][k] += mod;
                a[j][k] %= mod;
            }
        }
    }

    for (int i = 1; i <= n; i++) {
        for (int j = n + 1; j <= n + n; j++) {
            cout << a[i][j] << " ";
        }
        cout << endl;
    }
}