P1962 斐波那契数列

好多同学看到这道题的名字，都被勾引过去了，实际上并不简单呢。

朴素做法是递推，复杂度 $O(n)$. 然而这道题的 $n$ 达到 $2^{63} \approx 10^{19}$，递推只能拿 60 pts.

一些同学想到了通项公式：

然而由于涉及实数，存在浮点精度问题，因此除非你手写高精度浮点，否则也无法通过。

想一下为什么这道题出现在 P3390 【模板】矩阵快速幂 ↗ 之后？正如上一篇题解中所说，一些情况下我们需要计算方阵的幂，而求解线性递推数列就是其中之一。

如果用 $F_i$ 表示斐波那契数列的第 $i$ 项，则 $F_0=0,\ F_1=1$，且 $F_{i}=F_{i-1}+F_{i-2},\ i\in\{2,3,\dots\}$.

考虑向量 $\begin{bmatrix*} F_i\\ F_{i-1} \end{bmatrix*}$，我们可以把上述递推公式写成矩阵向量乘法的形式：

因此，求解 $F_n$ 就可以看作使用 $\boldsymbol{A}^{n-1}$ 去左乘 $\begin{bmatrix*} F_1\\ F_{0} \end{bmatrix*}=\begin{bmatrix*} 1\\ 0 \end{bmatrix*}$，可以 $O(\log n)$ 地求解。

特别地，由于 $\begin{bmatrix*} 1\\ 0 \end{bmatrix*}$ 可以看作取 $\boldsymbol{A}^{n-1}$ 的第一列，因此直接计算 $\boldsymbol{A}^{n-1}$ 即可，然后取左上角的元素。

ll n;
struct Matrix; // Matrix 定义见前一篇题解
Matrix a,ans;

int main()
{
	cin>>n;
    n--;
    a.m=a.n=ans.m=ans.n=2;
    a[1][1]=a[1][2]=a[2][1]=ans[1][1]=ans[2][2]=1; // 初始化矩阵，a 为 A 矩阵，ans 为单位矩阵
    while(n)
    {
        if(n&1)
        {
            ans*=a;
        }
        a*=a;
        n>>=1;
    }
    cout<<ans[1][1]%Mod;
    return 0;
}