Hzao's Blog – 第4页 – Based on WordPress

矩阵乘法

写在最前面的话

由于自己太弱了，写这个来总结一下，方便复习。很多内容总结自维基百科（链接1、链接2）和李煜东《算法竞赛进阶指南》。

适用范围

一个矩阵的列数等于另一个矩阵的行数时，它们的乘法才有意义。

运算方法

对于一个 $n*p$ 的矩阵 $A$ 和一个 $p*m$ 的矩阵 $B$ ，它们的乘积 $C$ 是一个 $n*m$ 的矩阵。

$A$ 矩阵和 $B$ 矩阵乘积中的元素 $C_{[i,j]}$ ,等于 $A$ 矩阵第 $i$ 行的 $p$ 个数和 $B$ 矩阵第 $j$ 列的 $p$ 个数分别相乘的和。即：

$C_{i,j} = \sum_{k=1}^{p} A_{i,k}*B_{k,j}$

矩阵乘法同数的乘法一样，有结合律、分配律。但是交换因数后不一定能满足 $(n*p)*(p*m)$ 的形式，即m不一定等于n，并且就算满足也不一定结果相等，所以矩阵乘法不满足乘法交换律。

纯乘法的代码实现

1.计算函数。由于自己太弱了，加上时间有限，写了一份很水的代码。

但是这里必须固定 $A$ 、 $B$ 的数组大小，可能vector可以解决这个问题？欢迎大佬们指教。

#include<cstdio>
int A[2][3]={
	{1,2,3},
	{4,5,6}
};
int B[3][4]={
	{1,2,3,4},
	{5,6,7,8},
	{9,10,11,12}
};
int c[2][4];
int n,m;
void mul(int a[][3],int b[][4],int n,int m,int p){
	for(int i=0;i<n;++i){//n 乘积的行数 
		for(int j=0;j<m;++j){//m 乘积的列数 
			for(int k=0;k<p;++k){//p 即共有的维 
				c[i][j]+=a[i][k]*b[k][j];
			}
			printf("c[%d][%d]=%d\n",i,j,c[i][j]);
		}
	}
}
int main(){
	mul(A,B,2,4,3);//计算A*B,并保存到c[][4]数组中 
	return 0;
}

2.有一种边读入边计算的写法：

	scanf("%lld%lld%lld",&n,&p,&m);
	for(long long i=1;i<=n;++i){
		for(long long j=1;j<=p;++j){
			scanf("%lld",&a[i][j]);
		}
	}
	for(long long i=1;i<=p;++i){
		for(long long j=1;j<=m;++j){
			scanf("%lld",&b[i][j]);
			for(long long k=1;k<=n;++k){//此处k枚举的并非是公共维
				ans[k][j]+=a[k][i]*b[i][j];
			}
		}
	}

需要注意的是，这里的k的含义与上一份代码不同。由于已经枚举了公共边（即第7行枚举的 $i$ ）和列数 $j$ ，这里只需要枚举乘积的行数。仍然是 $n*m*p$ 三维。

~~我也不知道自己怎么就写了这么个没用的玩意。~~

用途

矩阵的一个重要用途是解线性方程组。线性方程组中未知量的系数可以排成一个矩阵，加上常数项，则称为增广矩阵。另一个重要用途是表示线性变换，即是诸如
$f(x)=4x$ 之类的线性函数的推广。
——维基百科

1.其实蒟蒻的我并不知道怎么解线性方程组，但是对于矩阵加速线性变换有一些体会。让我们考虑一种比较特殊的矩阵乘法： $1*n$ 和 $n*n$ 。由定义可知，它们的乘积仍然是一个 $1*n$ 的矩阵。那么有什么用呢？我们可以借助快速幂的思想，利用矩阵乘法的分配律、结合律，降低时间复杂度。

例如，POJ3070 这道题要求斐波那契数列第 $n$ 项mod $m$ （给定 $n$ , $m$ ）的值。我们可以设一个 $1*2$ 的矩阵 $A$ 来存放 $F_{i},F_{i+1}$ ，然后通过设立方程，求出一个 $2*2$ 的矩阵 $B$ ，使得 $A*B$ 得到的 $1*2$ 的矩阵 $C$ ，满足 $C=[F_{i+1},F_{i+2}]$ 。于是，我们可以把时间复杂度由 $O(n)$ 降低到 $O(log_{2}^{n})$ 。
我们可以通过设未知数解方程，使一个矩阵满足一定的性质。例如，当我们写快速计算矩阵乘法的函数时，函数里默认的矩阵（用于存放答案）应该初始化为什么呢？（计算快速幂时将对应变量初始化为1）如果全部初始化为0，就会导致任何符合条件的矩阵与其相乘都为0。

通过解方程，可以发现，一个 $2*2$ 的矩阵

$\left[ \begin{matrix} 1 & 0 \\ 0 & 1 \\ \end{matrix} \right]$

与任何一个满足 $x==2$ 的 $x*y$ 的矩阵相乘，结果仍然等于这个 $x*y$ 的矩阵。

因此，我们可以把这个矩阵初始化为如上的矩阵，其作用等同于计算快速幂时的1；

2.以后遇到再来补充。

.

我觉得现在的喜剧电影还不如科幻甚至恐怖电影好笑，所谓笑点和煽情对白简直反智，就像是把几千个土味视频强行用一个剧情连起来一样。

又睡不着

北京时间2019年2月6日02:38，再一次睡不着的我又来翻一下手机。因为躺着等睡意除了可以突然得到一些白天再想起就会被自己否定的灵感外，还不如做点别的事情睡意来得快，只不过代价是心脏会疼两下。

垃圾短信已然突破722条，短短几天多了将近60条，可能我太受人喜欢了。

去年（或者前年）以前，光顾一些店的时候，人家都会叫我“H同学”。大概从去年（或者前年）开始，就变成了“H先生”。当时觉得自己真的老了。前几日成都行，成都人又把我叫“H同学”。也就罢了吧，今天（准确来说是昨天）去万达某店再次光顾，曾经一度叫我“H先生”的小伙伴居然再次叫起了“H同学”，甚至在另一家店买福袋还被问“你上初中还是高中啊”这样的问题——果然是这几天懒觉把我睡年轻了。

不过已经设置好7:30开始的连环闹钟，牺牲一点睡觉的时间，希望能从今天开始早睡早起。

第666条垃圾短信

恭喜Hzao喜提第666条垃圾短信

燃点

绵阳市早就没有《燃点》的排片了，于是今天坐动车到成都看。刚进场的时候加上我一共只有两个人，后来陆陆续续来了八九个人，应该是组团来的。

结束之后他们请我帮他们拍照，我以为他们是专门来看谁的，拍完之后问：“你们是来看谁的？”他们答：“我们不是来看谁的。”其中一位反过来问我是来看谁的，我说我看罗永浩。

于是，一个男生说：“罗永浩……”拖长“浩”字后停下，总之是想说点什么，但是也许是出于礼貌没有说出来。

我应该知道他想说什么的。

于是和鲁迅“惨象，已使我目不忍视了。流言，尤使我耳不忍闻”的感受再次一样了。

睡不着

有些bad feelings，需要调整一下心情再睡。

我不是那种可以选择性忘记或者无视一些东西而让自己获得短暂安心和快乐的人。但我不觉得这是缺点，这应该是一种特质。只是有些时候会羡慕那些心态很好能放下顾忌的人们。