【算法】矩阵快速幂
【题解】
根据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<cstdio>
#include<algorithm>
#include<cstring>
using namespace std;
const int n=,MOD=;
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=;i<n;i++)
for(int j=;j<n;j++)
{
t[i][j]=;
for(int k=;k<n;k++)
t[i][j]=(t[i][j]+a[i][k]*b[k][j])%MOD;
}
for(int i=;i<n;i++)
for(int j=;j<n;j++)
ans[i][j]=t[i][j];
}
int main()
{
scanf("%d",&m);
while(m!=-)
{
if(m==){printf("0\n");scanf("%d",&m);continue;}
m--;
a[][]=a[][]=a[][]=;a[][]=;
b[][]=;b[][]=b[][]=b[][]=;
while(m>)
{
if(m&)mul(a,b,b);
m>>=;
mul(a,a,a);
}
printf("%d\n",b[][]);
scanf("%d",&m);
}
return ;
}
可以发现|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（可以是负数）。