P1962 斐波那契数列-题解（矩阵乘法扩展）

https://www.luogu.org/problemnew/show/P1962(题目传送)

n的范围很大，显然用普通O(N)的递推求F(n)铁定超时了。这里介绍一种用矩阵快速幂实现的解法：

首先普及一下矩阵乘法：

一个m*q的m行q列的矩阵A*一个q*n的q行n列的矩阵B得到一个m*n的m行n列的矩阵AB,则有:

通俗的讲，就是新矩阵第i行j列的数等于第一个矩阵第i行的q个数分别乘第二个矩阵的第j列的q个数并把它们加起来的和。注意，矩阵乘法满足结合律和分配律，但不满足交换律。

我们可以把第n项F(n)、第n-1项F(n-1)写成一个1*2的矩阵[Fn  ​​Fn-1] 并考虑怎样由前面的[Fn-1  ​​Fn-2]推过来。可以先把[Fn  ​​Fn-1]写成[1*Fn-1+1*Fn-2  ​​1*Fn-1+0*Fn-2]的形式，试推导一个矩阵base，使

[Fn-1  ​​Fn-2