矩阵快速幂求菲波那切数列第N项

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
#include<bits/stdc++.h>
using namespace std;
#define int long long
typedef long long ll;
const int m=1e9+7;
int n;
ll A[2][2] = {      // 用于快速幂的矩阵
    {0, 1},
    {1, 1}
};
ll res[2] = {2, 3}; // 用于存答案的矩阵（转置）
// 计算列矩阵 A 乘方阵 B 的乘积，并存储在 A 中
// 1 * 2矩阵与 2 * 2 矩阵相乘
void _multi(ll A[], ll B[][2])
{
    ll ans[2] = {0};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            ans[i] += A[j] * B[i][j] % m;
    for (int i = 0; i < 2; i ++ )
        A[i] = ans[i] % m;
}
// 计算方阵 A 乘方阵 B 的乘积，并存储在 A 中
// 2 * 2 矩阵与 2 * 2 矩阵相乘
void multi(ll A[][2], ll B[][2])
{
    ll ans[2][2] = {0};
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            for (int k = 0; k < 2; k ++ )
                ans[i][j] += A[i][k] * B[k][j] % m;
    for (int i = 0; i < 2; i ++ )
        for (int j = 0; j < 2; j ++ )
            A[i][j] = ans[i][j] % m;
}
signed main()
{
    cin>>n;// m=1e9+7;
if(n==0) {cout<<1;return 0;}
  n--;
    while (n) // 矩阵快速幂板子
    {
        if (n & 1) _multi(res, A);
        multi(A, A);
        n >>= 1;
    }
  cout<<res[0]; // 最后 res[0] 即为 f[n] 的结果
    return 0;
}