让我们来看一道题
有如下数列：
给你a和b，求出数列中第a项对b的余数，a/b<2^63-1

我们知道上述数列是著名的Fibonacci数列。
朴素解是显然的O(a)算法，即朴素遍历出数列并求余
显然的这个算法会超时，我们需要更高级的算法

让我们观察这个数列

能想到什么呢？
尝试着用一个矩阵来表示
因为Fibonacci数列的特殊性，我们自然要问，这个矩阵和第x-1，x-2项有什么关系？
显然的，有
根据Fibonacci数列递推式和矩阵乘法的定义，我们显然的会发现A的取值

注意到矩阵乘法是满足交换律的
那么上述式子有如下形式

其中f(2),f(1)的值早已给出

这个式子有什么作用呢？
下面就必须要介绍快速幂了。
对于一个a^b的式子，显然的有a^b=[a^(b/2)]*[a^(b/2)]
那么我们就可以用分治算法在O(kloga)的时间内计算出A^a的值了（k是矩阵乘法的时间）
给出c++代码
struct
jz{
int da[2][2];
};
jz quick(int b)
{
if(b==1)
return A;
if(b==0)
return C;
int je=b%2;
jz tu=quick(b/2);
if(je==0)
return tu*tu;
else
return tu*tu*A;
}
C矩阵=
矩阵乘法的算符重载就不写了……
注意到对于这样的小矩阵，k完全可以被视作常数隐藏在O记号中
那么我们就得到了一个O(loga）的算法！

矩阵加速是非常强大的……具体功能请自己探寻。
顺带一提的是，矩阵乘法除了O(n^3)的算法外，还有称作strassen的高速算法
可以达到theta(n^log7)的算法
但其实这是个伪.快速算法，同时还面对着精度问题
1 在Strassen算法的运行时间中，隐含的常数因子比简单的O(n^3)方法常数因子大
2 当矩阵是稀疏的时候，为稀疏矩阵设计的算法更快
3 Strassen算法不像简单方法那样子具有数值稳定性
4 在递归层次中生成的子矩阵要消耗空间。
在这里不多介绍……对于这样的矩阵完全没有使用它的必要。
END.

P.s
对于矩阵乘法，一个显然的下界是O(n^2)，因为我们必须要填写结果矩阵的n^2个元素

@qsd573

为什么要把向量横着写
而且算符写在右边