矩阵(神奇算法)
昨晚学长教了我们这样一个神奇的算法---矩阵快速幂，矩阵快速幂在递推优化上相当神奇，并且效率很高。
一、 先举这样一个例子。斐波那契数列大家都知道的吧。f[n]=f[n-1]+f[n+2](n=108),求f[n];
这种题目，要是用递归做下去肯定超时。但是用矩阵就很容易解决。
f[n] * 0 1 = f[n+1]
f[n+1] ...A 1 1 ...C f[n+2] ...B A矩阵*C矩阵得到B矩阵。C矩阵是推出来的；主要的核心就是推出一个矩阵与A得到B矩阵。(即我知道当前状态和下一状态，我就要求出中间的媒介，这样的话就是可以无限知道下下状态，下下下状态....的值~~)我们知道f[1]=1,f[2]=1; A*Cn=B,接着对Cn快速幂取模就OK了！
略懂一点之后，转变一下。
二、有a,b,c,d四个城市，如同所示。
求从a->d在正好n步的条件下走到。n很大很大。求有多少种方法。
这个的初始的是走0步到达下一个位置的矩阵A=E（单位矩阵），然后很明显的中介矩阵就是 a b c d
a 0 1 1 0
b 0 0 1 1
c 1 1 0 1
d 0 1 1 0....C 然后A*C就可以得到走两步到一个地方的种数。其中"1"表示a->b有一种方法。
三、依旧是有a，b，c，d四个城市，如图所示。
我现在要从a到d在正好n步的条件下走到，加一个要求就是路程最短。求最短的路程。和上一个类似，这里就不进行详解了0.0
学长还讲了区域赛里的几个题目，一时半会说不清楚，从早上总结到现在，该去吃饭了==总结一下吧
矩阵快速幂主要的就是要写出那三个矩阵来解决问题，虽然现在讲的只是一种思想，里面掺杂一些动态规划的问题，不过是很实用的，可以很快速的来解决n值特别大，或者类似的组合问题。
郑重声明：本站内容如果来自互联网及其他传播媒体，其版权均属原媒体及文章作者所有。转载目的在于传递更多信息及用于网络分享，并不代表本站赞同其观点和对其真实性负责，也不构成任何其他建议。
