题目链接：传送门

Description

求出斐波那契第N项(N<=2642^{64}Mod 1000000007的值

Solution

我们可以用矩阵快速幂优化递推 首先我们易得： (F[N+1]F[N]F[N]F[N−1])=(1110)×(F[N]F[N−1]F[N−1]F[N−2])\begin{pmatrix}F[N+1]& F[N] \\ F[N] & F[N-1] \end{pmatrix} = \begin{pmatrix}1&1\\ 1& 0\end{pmatrix} \times \begin{pmatrix}F[N]& F[N-1] \\ F[N-1] & F[N-2] \end{pmatrix} 所以我们就有： (F[N+1]F[N]F[N]F[N−1])=(1110)N\begin{pmatrix}F[N+1]& F[N] \\ F[N] & F[N-1] \end{pmatrix} = \begin{pmatrix}1&1\\ 1& 0\end{pmatrix} ^N 然后我们用矩阵快速幂处理即可

Code

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
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long long
using namespace std;
const int Mod = 1000000007; 
LL N, M;
LL bas[5][5], ans[5][5], tmp[5][5];
inline LL read()
{
    char ch = getchar();
    while (ch < '0' || ch > '9')ch = getchar();
    LL sum = ch - '0';
    ch = getchar();
    while (ch >= '0' && ch <= '9') {sum = sum * 10 + ch - '0'; ch = getchar();}
    return sum;
}
inline void Matrix_mult (int fl)
{
    if (fl)
    {
        for (int i = 1; i <= 2; ++ i)
            for (int j = 1; j <= 2; ++j)
                tmp[i][j] = ans[i][j],ans[i][j]=0;  
        for (int i = 1; i <= 2; ++ i)
            for (int j = 1; j <= 2; ++ j)
                for (int k = 1; k <= 2; ++ k)
                    (ans[i][j] += (tmp[i][k] * bas[k][j]) % Mod) %= Mod;
    }
    else
    {
        for (int i = 1; i <= 2; ++ i)
            for (int j =1; j <= 2; ++j)
                tmp[i][j] = bas[i][j],bas[i][j]=0;
        for (int i = 1; i <= 2; ++ i)
            for (int j = 1; j <= 2; ++ j)
                for (int k = 1; k <= 2; ++ k)
                    (bas[i][j] += (tmp[i][k] * tmp[k][j]) % Mod) %= Mod;
    }

}
inline void Matrix_pow ()
{
    while (N)
    {
        if (N & 1) Matrix_mult(1);
        Matrix_mult(0);
        N >>= 1;
    }
}
int main()
{
#ifndef ONLINE_JUDGE
    freopen("a.in", "r", stdin);
    freopen("a.out", "w", stdout);
#endif
    N = read();
    bas[1][1] = 1;bas[1][2] = 1;bas[2][1] = 1;
    ans[1][1] = 1;ans[1][2] = 1;ans[2][1] = 1;ans[2][2] = 1;
    N--;
    Matrix_pow();
    printf("%lld\n", ans[1][2]);
    return 0;
}