P1962 斐波那契数列

发表于 更新于 分类于 ，

题目描述

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

$$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 + 7 的值。

输入格式

一行一个正整数 n。

输出格式

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

输入输出样例 #1

输入 #1

1
5

输出 #1

1
5

输入输出样例 #2

输入 #2

1
10

输出 #2

1
55

说明/提示

【数据范围】
对于 60% 的数据，1 ≤ n ≤ 92；
对于 100% 的数据，1 ≤ n < 263。

解析

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

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

这里是 2x2 的矩阵乘法

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

$$ C_{i,j} = \sum_{k=1}^n A_{i,k} \times B_{k,j} $$

那么假设我们有一个矩阵

$$ A = \begin{bmatrix} 1 & 1 \\ 0 & 0 \end{bmatrix} $$

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

$$ C = \begin{bmatrix} 2 & 1 \\ 0 & 0 \end{bmatrix} $$

我们可以利用一个因子

$$ B = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} $$

$$ AB = \begin{bmatrix} 1\times1+1\times1 & 1\times1+1\times0 \\ 1\times0+1\times0 & 1\times0+0\times0 \\ \end{bmatrix} $$

可以得到

$$ C = \begin{bmatrix} 2 & 1 \\ 0 & 0 \end{bmatrix} $$

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

$$ A = \begin{bmatrix} a & b \\ 0 & 0 \end{bmatrix} $$

$$ B = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix} $$

则

$$ AB = \begin{bmatrix} a\times1+b\times1 & a\times1+b\times0 \\ a\times0+b\times0 & a\times0+b\times0 \\ \end{bmatrix} $$

即

$$ C = \begin{bmatrix} c & a \\ 0 & 0 \end{bmatrix} $$

则因为 Cn = ABn − 2，所以可以使用快速幂求 Bn − 2，然后与 A 相乘即可。

上代码

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;
}