题解 P1962 【斐波那契数列】

EricQian · 2019-10-06 17:16:10 · 题解

直接循环递推斐波那契数列，时间复杂度显然为 O(n) 。不过，Fib_n 只与 Fib_{n-1} 与 Fib_{n-2} 有关，我们在递推的时候只需要保存最近的两个斐波那契数，即可得到下一个斐波那契数。

设 F(n) 表示一个 1 * 2 的矩阵，F(n)=[Fib_{n-1},Fib_{n-2}] 。

我们希望根据 F(n-1)=[Fib_{n-1},Fib_{n-2}] 计算出 F(n) 。也就是说，要把 F(n-1) 第 1、2 列上的数都累加到 F(n) 的第二列上。因此，我们令 A 第 2 行第 1 列、第 2 行第 2 列、第 1 行第 2 列都是 1，第 1 行第 1 列的数是 0。

上式是一个矩阵乘法递推式，初值 F(n)=[0,1] ，目标为F(n)=F(0) * A^n。因为矩阵乘法满足结合律，所以我们可以用快速幂计算 F(n) * A^n ,得到的矩阵第一列上的数就是 Fib_n 。算法的时间复杂度为 O(2^3log_2^n) ，其中 2^3 是矩阵乘法所消耗的时间。

题目还要求我们对一个大数取模，可以直接在执行时加入取模运算。详细过程请见下面示例代码：

#include<bits/stdc++.h>
using namespace std;
#define mol 1000000007
long long n;
long long a[2][2]={{0,1},{1,1}},A[2][2];
long long f[2]={0,1},F[2];
void muladd()
{
     memset(F,0,sizeof(F));
     for(int i=0;i<2;i++)
         for(int k=0;k<2;k++)
             F[i]=(F[i]+f[k]*a[k][i])%mol;
     memcpy(f,F,sizeof(F));
     return;
}
void mul()
{
     memset(A,0,sizeof(A));
     for(int i=0;i<2;i++)
         for(int j=0;j<2;j++)
             for(int k=0;k<2;k++)
                 A[i][j]=(A[i][j]+a[i][k]*a[k][j])%mol;
     memcpy(a,A,sizeof(A));
     return;
}
int main()
{
     scanf("%lld",&n);
     while(n) // 快速幂
     {
         if(n%2) muladd();
         mul();
         n/=2;
     }
     printf("%d\n",f[0]%mol);
     return 0;
}