来聊聊如何将快速幂的思想应用到矩阵乘法上， 以及矩阵快速幂的应用。

矩阵快速幂

矩阵乘法

在线性代数中学过， n行x列的矩阵A与x行m列的矩阵B是可以相乘的， 结果为一个n行m列的矩阵R， 且.

而对于方阵, 又有幂的概念， , 即n个M矩阵相乘.

最近发现了一个很有意思的网站：codewars， 上面有很多有趣的'kata'， 通过kata可以提升你的段位。

codewars上的题目和传统的竞赛题目的风格不太一样， 而且用户是可以创建kata的， 这一点我觉得很有意思。

在codewars中老是遇到高精度的题目(高精度在普通OJ中基本只有模板题)， 每次都要手写及处理细节十分的腻，于是决定把高精度好好的写一遍记录下来， 供未来copy。

最短路径问题是图论研究中的一个经典算法问题，旨在寻找图（由结点和路径组成的）中两结点之间的最短路径。

单源最短路

即对确定的源点（起点）， 求它到其它所有可达的点的最短路径。 对于单源最短路算法， 又可以分为处理正权边图和带负权边图的两种。

没什么写， 突发奇想总结一下以前写过的排序算法， 权当复习。

以下皆以升序举例， a为默认数组名， n默认为数组长度

冒泡排序

大多数人学的第一个排序算法就算冒泡排序， 思想是每次比较相邻的两个数， 如果与升序不符合就进行交换； 从前到后一轮交换下来， 不难发现最大值会被交换到最后位， 因此下次只需要对前n-1个元素进行遍历即可。

每轮交换至少确定一个数的位置， 所以最多需要进行n - 1轮, 时间复杂度为

线段树简介

线段树常用来解决多次区间修改以及区间性质查询的问题， 且区间的性质一般可以由子区间推出， 如最大值、区间和。

线段树的结构

线段树顾名思义显然是一棵树， 且一般实现为二叉树。 线段树满足：

• 树上每一个结点都代表着一段区间

• 每个结点的两个子结点分别代表该区间的左右子区间。