矩阵快速幂

矩阵的快速幂是用来高效地计算矩阵的高次方的。将朴素的o（n）的时间复杂度，降到log（n）.

最简单的例子来讲，一般我们正常计算实数x的n次幂时，都是从1开始，进行n次的x相乘。

但做下简单的改进就能减少连乘的次数，方法如下：

把n个矩阵进行两两分组，比如：A*A*A*A*A*A => (A*A)*(A*A)*(A*A)

这样变的好处是，你只需要计算一次AA，然后将结果(AA)连乘自己两次就能得到A^6，即(A*A)^3=A^6.这样就很容易的实现了时间复杂度的优化。

在上面的问题中，最重要的就是如何选择间距值，上面的解答给我们展示了间距为2的示例，但我们还可以有很多其他的选择。那么如何选择出时间复杂度最低的呢，我们应该充分的使用现有的计算结果

回头看看矩阵的快速幂问题，我们是不是也能把它离散化呢？比如A^19 => （A^16）（A^2）（A^1），显然采取这样的方式计算时因子数将是log(n)级别的(原来的因子数是n)，不仅这样，因子间也是存在某种联系的，比如A^4能通过(A^2)(A^2)得到，A^8又能通过(A^4)(A^4)得到，这点也充分利用了现有的结果作为有利条件。

下面举个例子进行说明：

现在要求A^156,而156(10)=10011100(2)

也就有A^156=>(A^4)(A^8)(A^16)*(A^128)

while(N)
 {
                if(N&1)
                       res=res*A;
                N>>=1;
                A=A*A;
 }