Codevs1732-矩阵乘法快速幂
矩阵的乘法有结合律但没有交换律,即(A*B)*C等于A*(B*C),但是A*B不等于B*A。由于矩阵的乘法支持结合律,所以可以利用快速幂的思想在O(logN)的时间内求出矩阵A ^ N。矩阵可以很好的表示线性递推关系。例如:f(n)=a1*f(n-1) + a2*f(n-2) + ······ + ad*f(n-d),则我们可以设矩阵:F(N)=|f(n-d+1) | ( 共d行1列) | ······ | | f(n-1) | | f(n) | 我们再设矩阵A=|0,1,0 ······ 0||0,0,1 ······ 0|| ····················· ||0,0,0 ······ 1||a1,a2,····ad|(共d行d列),则存在下列关系A*F(N-1)=F(N)。于是我们就可以通过计算A的幂来快速求F(N)了。贴一个codevs1732的标程:
来源: http://www.bubuko.com/infodetail-1978913.html