P1962 斐波那契数列

题目传送门

一、矩阵分析

\[\begin{bmatrix} F(n)\\ F(n-1) \end{bmatrix} =\begin{bmatrix} F(n-1)+F(n-2)\\ F(n-1) \end{bmatrix}=\begin{bmatrix} F(n-1) * 1 + F(n-2)*1\\ F(n-1) * 1 + F(n-2) * 0 \end{bmatrix}=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} F[n-1]\\ F[n-2] \end{bmatrix} \]

\[\begin{bmatrix} F(n)\\ F(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} F(n-1)\\ F(n-2) \end{bmatrix} \\ \begin{bmatrix} F(n-1)\\ F(n-2) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}\begin{bmatrix} F(n-2)\\ F(n-3) \end{bmatrix} \\ \begin{bmatrix} F(n)\\ F(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^2\begin{bmatrix} F(n-2)\\ F(n-3) \end{bmatrix}\]

以此类推

\[\begin{bmatrix} F(n)\\ F(n-1) \end{bmatrix} = \begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}^{n-2}\begin{bmatrix} F(2)\\ F(1) \end{bmatrix} \]

所以要求斐波那契的第\(n\)项，我们只需要求得\(F(2)\)和\(F(1)\)构成的矩阵与特定矩阵的\(n-2\)次方相乘后的矩阵，然后取该矩阵的第一行第一列的元素值就是\(F(n)\)

二、实现代码I

#include 
using namespace std;
typedef long long LL;
const int N = 10;
const int MOD = 1e9 + 7;

//矩阵声明
struct JZ {
    LL m[N][N];
} res, base;

inline JZ mul(JZ A, JZ B) {
    JZ C;
    memset(C.m, 0, sizeof(C.m));
    for (int i = 1; i <= 2; i++)
        for (int j = 1; j <= 2; j++)
            for (int k = 1; k <= 2; k++) {
                C.m[i][j] = (C.m[i][j] + (A.m[i][k] * B.m[k][j]) % MOD) % MOD;
            }
    return C;
}

//快速幂
inline void qmi(LL k) {
    memset(res.m, 0, sizeof res.m);
    res.m[1][1] = res.m[1][2] = 1; // f(1)=1,f(2)=1 乘一次矩阵就是f(3),所以f(n)就是n-2次方
    while (k) {
        if (k & 1) res = mul(res, base);
        base = mul(base, base);
        k >>= 1;
    }
}
int main() {
    LL n;
    cin >> n;
    if (n <= 2) {
        puts("1");
        return 0;
    }
    //结果矩阵初始化
    memset(base.m, 0, sizeof base.m);
    base.m[1][1] = base.m[1][2] = base.m[2][1] = 1;
    /*
    1 1
    1 0
    base 矩阵
    */
    //快速幂
    qmi(n - 2);
    //结果
    cout << (res.m[1][1]) % MOD << endl;
    return 0;
}

三、实现代码II

#include 
using namespace std;
typedef long long LL;
const int N = 10;
const int MOD = 1e9 + 7;

LL base[N][N], res[N][N];

inline void mul(LL C[][N], LL A[][N], LL B[][N]) {
    static LL tmp[N][N];
    memset(tmp, 0, sizeof(tmp));
    for (int i = 1; i <= 2; i++)
        for (int j = 1; j <= 2; j++)
            for (int k = 1; k <= 2; k++)
                tmp[i][j] = (tmp[i][j] + (A[i][k] * B[k][j]) % MOD) % MOD;
    memcpy(C, tmp, sizeof tmp);
}

//快速幂
inline void qmi(LL k) {
    //初始化结果数组的(i,i)=1
    memset(res, 0, sizeof res);
    res[1][1] = res[1][2] = 1;
    while (k) {
        if (k & 1) mul(res, res, base);
        mul(base, base, base);
        k >>= 1;
    }
}

int main() {
    LL n;
    cin >> n;
    if (n <= 2) {
        puts("1");
        return 0;
    }
    //结果矩阵初始化
    memset(base, 0, sizeof base);
    base[1][1] = base[1][2] = base[2][1] = 1;
    //快速幂
    qmi(n - 2);
    //结果
    cout << (res[1][1]) % MOD << endl;
    return 0;
}