题面

题目背景

大家都知道，斐波那契数列是满足如下性质的一个数列：

• f(1) = 1

• f(2) = 1

• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)

题目描述

请你求出 f(n) mod 1000000007 的值。

输入格式：

·第 1 行：一个整数 n

输出格式：

第 1 行： f(n) mod 1000000007 的值

输入输出样例

输入样例#1：

5

输出样例#1：

5

输入样例#2：

10

输出样例#2：

55

说明

对于 60% 的数据： n ≤ 92

对于 100% 的数据： n在long long(INT64)范围内。

题解

看一看数据范围

如果使用O(n)的递推显然会炸掉

那么我们有没有别的方法？

显然是有的

使用斐波那契数列的递推公式怎么样?

但是，，，里面带有根号，如果直接使用显然是会掉精度的

所以，，，应该怎么办

我们知道

f[i]=f[i-1]+f[i-2]

f[i-1]=f[i-2]+f[i-3]

所以

我们可以用矩阵来表示

因此

我们可以继续推导

可以得到

接下来使用矩阵快速幂就可以直接求解

#include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          using namespace std;#define MOD 1000000007#define MAX 10#define ll long longstruct yl//矩阵 { int n;//大小 long long g[MAX][MAX]; };yl operator *(yl a,yl b)//定义乘法 { int n=a.n; yl cool; memset(cool.g,0,sizeof(cool.g)); for(int i=1;i<=n;++i) for(int j=1;j<=n;++j) for(int k=1;k<=n;++k) cool.g[i][j]=(cool.g[i][j]+1ll*a.g[i][k]*b.g[k][j]%MOD)%MOD; cool.n=n; return cool;}void write(yl a){ int n=a.n; for(int i=1;i<=n;++i) { for(int j=1;j<=n;++j) cout<
          
           <<' '; cout<
           
            >n; if(n==0) { cout<<0<