首先我们要了解一下矩阵乘法： 恩恩~啊啊~亚美爹~不要~恩~不要~
当然楼上的娇喘过度，显然是不靠谱的，我还是自己讲吧。 首先来讲一下矩阵的定义，其实就是按照长方形排列的实数或复数集合，在编程语言中可以看做是二维数组咯。一般我们可以叫它Matrix。
然后是矩阵的运算，我们当前应接触的有四种：加、减、数乘、乘 加是什么呢？就是把两个矩阵的对应位置加起来，得到一个新的矩阵，减类似。但要注意，加减的运算，两个矩阵必须是一样规模的，即n*m。比如：
[122333]+[415266]=[537599]
好哦，减法是一样的，那么接下来就是数乘。 格式是 n∗矩阵 ，作用是把矩阵的每个数字乘上 n
4∗⎡⎣⎢531752993⎤⎦⎥=⎡⎣⎢2012428208363612⎤⎦⎥
好了，接下来就是最难也是最有用的矩阵乘法了！ 其实也很简单，但有个限制，必须是 n∗m 的矩阵和 m∗k 的矩阵相乘，也就是第一个矩阵的列数和第二个矩阵的行数相等，而答案矩阵会是一个n*k的矩阵。设 A=n∗m，B=m∗k 那么答案矩阵的第i行j个可以表示为：
(AB)ij=∑x=1mAixBxj=Ai1B1j+Ai2B2j+...+AimBmj 举个例子： [1−10321]∗⎡⎣⎢321110⎤⎦⎥=[3+0+2−3+6+11+0+0−1+3+0]=[5412]就是这个样子。但是关于矩阵，有加法交换律、加法结合律、乘法结合律，然而并没有乘法交换律，你懂的。
然后就是简单说一下快速幂，其实就是把那个次方递归成两个或三个小的部分。比如： 28=24∗24=22∗22∗22∗22=... 或者 25=22∗22∗2 反正就是这样啦。
接下来说一下很水的水题： 最短的水题（Fibonacci） （1s，256M） 1，1，2，3，5…..好熟悉的斐波拉契数列，请输出斐波拉契数列的第n项。 输入格式 一个数 n 输出格式 一个数 斐波拉契数列的第n项 ，答案摸10000007； 输入样例 4 输出样例 3 数据范围 50% 0<n<=100000; 100% 0<n<=1000000000000
恩，很大，然而用快速幂+矩阵乘法就行了。 我们可以这样想：
[F[i−1]F[i−2]]∗A=[F[i]F[i−1]]那么A是什么呢？我们就想，首先它肯定是一个 2∗2 的矩阵，然后 F[i−1] 乘一个数加 F[i−2] 乘一个数等于 F[i] ，显然都是1。同理，A矩阵的第二列我们只需要一个1，就能得到F[i-1]，也就是说我们最后的A矩阵是这样的：
[1110]然后我们用快速幂把这个矩阵乘个n次方就好啦。 时间复杂度是 O(len3∗logn)
其它拓展运用先不说啦~
