【数学】矩阵加速与斐波那契(fib)

注：本文只适用于C++

一、斐波那契数列的定义：

1. f i b 1 = f i b 2 = 1 , f i b n = f i b n − 1 + f i b n − 2 fib_1 = fib_2 = 1, fib_n = fib_{n - 1} + fib_{n - 2} fib1​=fib2​=1,fibn​=fibn−1​+fibn−2​ 2. f i b n = 5 [ ( 1 + 5 2 ) n − ( 1 + 5 2 ) n ] 5 fib_n = frac {sqrt5 left[left(frac{1 + sqrt 5}{2}right)^n - left(frac{1 + sqrt 5}{2}right)^nright]}{5} fibn​=55 ​[(21+5 ​​)n−(21+5 ​​)n]​

二、求解方法：
1.递归求解，运用递推式递归求解，算法时间复杂度 O ( 2 n ) O(2^n) O(2n)

long long fib(int n) {
    if (n <= 2) return 1;
    else return fib(n - 1) + fib(n - 2);
}

2.线性递推，递推式线性递推，算法时间复杂度 O ( n ) O(n) O(n)

long long fib(int n) {
    int a = 1, b = 1, t;
    for (int i = 3; i <= n; i++) t = a, a = b, b = a + t;
}

3.矩阵加速
经过复杂的递推，我们得到：

所以我们可以用矩阵快速幂与矩阵乘法解出。

#include 
#define ll long long
typedef struct  { ll c[2][2];} m;
using namespace std;
m operator* (m a, m b) {
    m res;
    memset(res.c, 0, sizeof(res.c));
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int z = 0; z < 2; z++)
                res.c[i][j] += a.c[i][z] * b.c[z][j];
    return res;
}
m pows(m a, ll n) {
    m I;
    I.c[0][0] = I.c[1][1] = 1, I.c[0][1] = I.c[1][0] = 1;
    while (n > 1) {
        if (n & 1) I = I * a;
        n >>= 1, a = a * a;
    }
    return I * a;
}
long long fib(int n) {
    m A, H;
    if (n <= 2) return 1;
    A.c[0][0] = 1, A.c[0][1] = 1, A.c[1][0] = 1, A.c[1][1] = 0;
    A = pows(A ,n - 2);
    H.c[0][0] = 1, H.c[0][1] = 0, H.c[1][0] = 1, H.c[1][1] = 0;
    A = A * H;
    return A.c[0][0];
}

有些题目数码很大需要取模，所以矩阵快速幂亦可取模，假设模10000，则代码变为

#include 
#define ll long long
typedef struct  { ll c[2][2];} m;
using namespace std;
const int mod = 10000 //此处为10000
m operator* (m a, m b) {
    m res;
    memset(res.c, 0, sizeof(res.c));
    for (int i = 0; i < 2; i++)
        for (int j = 0; j < 2; j++)
            for (int z = 0; z < 2; z++) {
                res.c[i][j] += a.c[i][z] * b.c[z][j];
                res.c[i][j] %= mod
            }
    return res;
}
m pows(m a, ll n) {
    m I;
    I.c[0][0] = I.c[1][1] = 1, I.c[0][1] = I.c[1][0] = 1;
    while (n > 1) {
        if (n & 1) I = I * a;
        n >>= 1, a = a * a;
    }
    return I * a;
}
long long fib(int n) {
    m A, H;
    if (n <= 2) return 1;
    A.c[0][0] = 1, A.c[0][1] = 1, A.c[1][0] = 1, A.c[1][1] = 0;
    A = pows(A ,n - 2);
    H.c[0][0] = 1, H.c[0][1] = 0, H.c[1][0] = 1, H.c[1][1] = 0;
    A = A * H;
    return A.c[0][0];
}