P1962 斐波那契数列

发表于 更新于 分类于 ，

题目描述

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

Fn={1 (n≤2)Fn−1+Fn−2 (n≥3)F_n = \left\{\begin{aligned} 1 \space (n \le 2) \\ F_{n-1}+F_{n-2} \space (n\ge 3) \end{aligned}\right.

请你求出 Fn mod 109+7F_n \bmod 10^9 + 7 的值。

输入格式

一行一个正整数 nn。

输出格式

输出一行一个整数表示答案。

输入输出样例 #1

输入 #1

1
5

输出 #1

1
5

输入输出样例 #2

输入 #2

1
10

输出 #2

1
55

说明/提示

【数据范围】
对于 60%60\% 的数据，1≤n≤921\le n \le 92；
对于 100%100\% 的数据，1≤n<2631\le n < 2^{63}。

解析

发现能找规律就很快，当然斐波那契公式也可以。

那么这里发现可以用矩阵乘法来做加法的工作，那么可能有人想问矩阵乘法的开销不是比普通二进制加法大N倍，但是我们可以快速幂啊！

这里是 2x2 的矩阵乘法

大概是这样的，矩阵乘法的结果C的 (i, j) 等于 矩阵A的第i行 与 矩阵B的第j列 的点积。
所谓点积，就是对应位置的元素相乘再相加。
也就是说

Ci,j=∑k=1nAi,k×Bk,jC_{i,j} = \sum_{k=1}^n A_{i,k} \times B_{k,j}

那么假设我们有一个矩阵

A=[1100]A = \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix}

其中(1,1) 和(2,1) 分别是斐波那契数列的第1项和第2项。
那么要得到斐波那契的下一项

C=[2100]C = \begin{bmatrix} 2 & 1 \\ 0 & 0 \end{bmatrix}

我们可以利用一个因子

B=[1110]B = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}

AB=[1×1+1×11×1+1×01×0+1×01×0+0×0]AB = \begin{bmatrix} 1\times1+1\times1 & 1\times1+1\times0 \\ 1\times0+1\times0 & 1\times0+0\times0 \\ \end{bmatrix}

可以得到

C=[2100]C = \begin{bmatrix} 2 & 1 \\ 0 & 0 \end{bmatrix}

注意到对于任意的 a=F(n),b=F(n−1),c=F(n+1)a=F(n), b=F(n-1), c=F(n+1)，若有

A=[ab00]A = \begin{bmatrix} a & b \\ 0 & 0 \end{bmatrix}

B=[1110]B = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}

则

AB=[a×1+b×1a×1+b×0a×0+b×0a×0+b×0]AB = \begin{bmatrix} a\times1+b\times1 & a\times1+b\times0 \\ a\times0+b\times0 & a\times0+b\times0 \\ \end{bmatrix}

即

C=[ca00]C = \begin{bmatrix} c & a \\ 0 & 0 \end{bmatrix}

则因为 Cn=ABn−2C_{n} = AB^{n-2}，所以可以使用快速幂求 Bn−2B^{n-2}，然后与 AA 相乘即可。

上代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include <iostream>
#include <cstring>
using namespace std;
const int mod = 1000000007;

struct Matrix{
    long long a[2][2];
    Matrix(){memset(a,0,sizeof a);}
    Matrix operator*(const Matrix b) const {
        Matrix r;
        for(int i=0;i<2;i++){
            for(int j=0;j<2;j++){
                for(int k=0;k<2;k++){
                    r.a[i][j] = (r.a[i][j] + a[i][k] * b.a[k][j]) % mod;
                }
            }
        }
        return r;
    }
    Matrix& operator*=(const Matrix b){
        return (*this)=(*this)*b;
    }
};

int calc(long long n){
    if(n<3) return 1;
    n -= 2;
    Matrix ans, base;
    ans.a[0][0] = ans.a[0][1] = base.a[0][0] = base.a[0][1] = base.a[1][0] = 1;
    while(n){
        if(n&1) ans *= base;
        base *= base;
        n >>= 1;
    }
    return ans.a[0][0];
}

int main(){
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    long long n;
    cin >> n;
    //for(int i=1;i<=n;i++)
        cout << calc(n) << endl;
    return 0;
}