【算法】矩阵快速幂

【题解】

根据f[n]=f[n-1]+f[n-2]，可以构造递推矩阵：

$$\begin{vmatrix}1 & 1\\ 1 & 0\end{vmatrix} \times \begin{vmatrix}f_n \\ f_{n-1} \end{vmatrix}=\begin{vmatrix}f_{n+1}\\f_n\end{vmatrix}\\$$

写成幂形式：

$$\begin{vmatrix}1 & 1\\ 1 & 0\end{vmatrix}^n \times \begin{vmatrix}1 \\ 0\end{vmatrix}=\begin{vmatrix}f_{n+1}\\f_n\end{vmatrix}$$

矩阵快速幂。

#include
      
       #include
       
        #include
        
         using namespace std;const int n=2,MOD=10000;int a[n][n],b[n][n],t[n][n],m;void mul(int a[n][n],int b[n][n],int ans[n][n]){    for(int i=0;i
         
          0)          {              if(m&1)mul(a,b,b);              m>>=1;              mul(a,a,a);          }         printf("%d\n",b[0][0]);         scanf("%d",&m);     }    return 0;}
         
        
       
      

 

可以发现|1 0|乘上之后没有任何变化，所以可以得到更好看的式子：

$$\begin{vmatrix}1 & 1\\ 1 & 0\end{vmatrix}^n=\begin{vmatrix}f_{n+1} & f_n\\ f_n & f_{n-1}\end{vmatrix}$$

用来推性质十分方便，适用于n∈Z（可以是负数）。