矩阵学习笔记-526互联

前言

蒟蒻刚刚开始学矩阵，有些东西可能理解得不是特别好。

矩阵的定义

在 $c$++ 中，矩阵其实就是一个 $n*m$，可以做运算的二维数组。也是运算的中的一种基本单位。

特殊的矩阵

在矩阵的运算过程中，可能会用到一些特殊的矩阵的名称，以下是比较常见的一些特殊矩阵：

同型矩阵：两个矩阵，行数与列数对应相同，称为同型矩阵。
方阵：$n*n$ 的矩阵。
乘法单位元：$a_{i,i} = 1$,其余位置为零的矩阵。
加法单位元：$a$ 数组全为零的矩阵。

矩阵的运算

矩阵加法

矩阵加法其实和正常的加法非常相似，对于两个同型矩阵 $a,b$，每一位的加法运算过程如下：

$ans_{i,j} = a_{i,j} + b_{i,j}$

矩阵乘法

矩阵乘法就和一般的乘法差别很大了，矩阵乘法相当于是用 $a$ 矩阵的列去乘 $b$ 矩阵的行，但乘法运算有一个前提：$a$ 矩阵的列数和 $b$ 矩阵的行数必须相等，否则运算无意义。 对于满足条件的两个矩阵，每一位的乘法运算过程如下：

设 $a$ 矩阵 $n*m$，$b$ 矩阵 $m*p$，则：

$ans_{i,j} = \sum_{i=1}^{n} \sum_{j=1}^{p} a_{i,k}*b_{k,j} $

Code

void mul()
{
	int ans[MAXN][MAXM] = {};
	for(int k = 1;k <= m;k++)
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= p;j++)
				ans[i][j] = (ans[i][j] + a[i][k] * b[k][j]) % mod;
	return;
}

矩阵快速幂

模板题：P3390
练习题：CF575A

当我们需要计算矩阵 $a^{k}$ 且 $k$ 十分大的时就，我们就需要用到矩阵快速幂了，思路和普通快速幂一样，不多赘述。不一样的就只是多了两个函数来计算矩阵乘法。

Code

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls id << 1
#define rs id << 1 | 1
#define inf 0x3f3f3f3f
typedef pair <int,int> pii;
const int MAXN = 1e2 + 10;
const int mod = 1e9 + 7;
int n,k,a[MAXN][MAXN],ans[MAXN][MAXN]; 
void mul1()
{
	int res[MAXN][MAXN] = {};
	for(int k = 1;k <= n;k++)
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= n;j++)
				res[i][j] = (res[i][j] + ans[i][k] * a[k][j]) % mod;
	for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) ans[i][j] = res[i][j];
}
void mul2()
{
	int res[MAXN][MAXN] = {};
	for(int k = 1;k <= n;k++)
		for(int i = 1;i <= n;i++)
			for(int j = 1;j <= n;j++)
				res[i][j] = (res[i][j] + a[i][k] * a[k][j]) % mod;
	for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) a[i][j] = res[i][j];
}
signed main()
{
	cin >> n >> k;
	for(int i = 1;i <= n;i++) for(int j = 1;j <= n;j++) cin >> a[i][j];
	for(int i = 1;i <= n;i++) ans[i][i] = 1;
	for(;k;k >>= 1){if(k & 1) mul1();mul2();}
	for(int i = 1;i <= n;i++) 
	{
		for(int j = 1;j <= n;j++) cout << ans[i][j] % mod << " ";
		puts(" ");
	}
    return 0;
}