【洛谷-P1962】斐波那契数列

题目地址：P1962 斐波那契数列 - 洛谷 | 计算机科学教育新生态 ↗

前置知识点

矩阵

定义：

一个 $n\times m$ 矩阵是由 $n\times m$ 个实数排列成 $n$ 行 $m$ 列构成的，用一对[]括起来。

下面 $3\times 3$ 矩阵简记为 $A=(a_{ij})_{3\times 3}$

A=\left[ \begin{matrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33}\\ \end{matrix} \right]

矩阵加减

$n$ 行 $m$ 列矩阵 $A,B$ 加减规则： $A\pm B=(a_{ij}\pm b_{ij})_{n\times m}$

矩阵加减满足交换律，结合律

\begin{aligned} A\pm B&= \left[\begin{matrix} a_{11}&a_{12}&\cdots&a_{1m}\\ a_{21}&a_{22}&\cdots&a_{2m}\\ \cdots&\cdots&\cdots&\cdots\\ a_{n1}&a_{n2}&\cdots&a_{nm}\\ \end{matrix}\right]\pm \left[\begin{matrix} b_{11}&b_{12}&\cdots&b_{1m}\\ b_{21}&b_{22}&\cdots&b_{2m}\\ \cdots&\cdots&\cdots&\cdots\\ b_{n1}&b_{n2}&\cdots&b_{nm}\\ \end{matrix}\right]\\&= \left[\begin{matrix} a_{11}\pm b_{11}&a_{12}\pm b_{12}&\cdots&a_{1m}\pm b_{1m}\\ a_{21}\pm b_{21}&a_{22}\pm b_{22}&\cdots&a_{2m}\pm b_{2m}\\ \cdots&\cdots&\cdots&\cdots\\ a_{n1}\pm b_{n1}&a_{n2}\pm b_{n2}&\cdots&a_{nm}\pm b_{nm}\\ \end{matrix}\right] \end{aligned}

矩阵乘法

**1.数和矩阵相乘

kA=Ak= \left[\begin{matrix} ka_{11}&ka_{12}&\cdots&ka{1m}\\ ka_{21}&ka_{22}&\cdots&ka{2m}\\ \cdots&\cdots&\cdots&\cdots\\ ka_{n1}&ka_{n2}&\cdots&ka{nm}\\ \end{matrix}\right]

2.矩阵和矩阵相乘

原理： $C_{ij}=A$ 的第 $i$ 行和 $B$ 的第 $j$ 列每个元素对应相乘的和。

所以矩阵乘法当且仅当A的列数=B的行数时才有定义。

由于矩阵乘法的规则， $A\cdot B\not= B\cdot A$

具体方法： $\textcolor{red}{C_{ij}}=a_{i1}b_{1j}+a_{i2}b_{2j}+\cdots+a_{it}b_{tj}=\textcolor{red}{\sum_{r=1}^{t}a_{ir}b_{rj}}$

实现

struct matrix {
   int n, m;
   int a[100][100];
};
// A.m == B.n
matrix matrix_mul(matrix A, matrix B) {
    matrix C;
    C.n = A.n;
    C.m = B.m;
    for (int i = 0; i < A.n; ++i) {
        for (int j = 0; j < B.m; ++j) {
            C.a[i][j] = 0;
            for (int k = 0; k < A.m; ++k) {
                C.a[i][j] += A.a[i][k] * B.a[k][j];
            }
        }
    }
    return C;
}

cpp

单位矩阵

形如：

\left[\begin{matrix} 1&0&\cdots&0\\ 0&1&\cdots&0\\ \cdots&\cdots&\cdots&\cdots\\ 0&0&0&1\\ \end{matrix}\right]

主对角线上元素均为1，其余元素均为0的矩阵。通常记做 $I_n$ 或 $E_n$

性质：

$A\cdot I_n=A$

$I_n\cdot A=A$

即任何一个矩阵左乘或右乘单位矩阵，结果不变（相当于乘法当中的 $1$ ）

矩阵快速幂

快速幂

int quick_power(int x,int y){
    int ans = 1,cnt = x;
    while(y){
        if(y & 1){
           ans *= cnt;
        }
        cnt *= cnt;
        y >>= 1;
    }
   return ans;
}

cpp

矩阵快速幂

利用快速幂思想，快速求矩阵 $A^n$

将快速幂中的乘法替换为矩阵乘法，参数和返回值替换为矩阵即可。

int n; // 所有矩阵都是 n * n 的矩阵
struct matrix {
   int a[100][100];
};
matrix matrix_mul(matrix A, matrix B, int mod) {
    // 2 个矩阵相乘
    matrix C;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            C.a[i][j] = 0;
            for (int k = 0; k < n; ++k) {
                C.a[i][j] = (C.a[i][j] + A.a[i][k] * B.a[k][j] % mod) % mod;
            }
        }
    }
    return C;
}
matrix unit() {
    // 返回一个单位矩阵
    matrix res;
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) {
                res.a[i][j] = 1;
            } else {
                res.a[i][j] = 0;
            }
        }
    }
    return res;
}
matrix matrix_pow(matrix A, int p, int mod) {
    // 快速求矩阵 A 的 p 次方
    matrix res = unit();
    while (p > 0) {
        if (p & 1) {
            res = matrix_mul(res, A, mod);
        }
        A = matrix_mul(A, A, mod);
        p >>= 1;
    }
    return res;
}

cpp

本题题解

斐波那契数列递推式：

a_n=a_{n-1}+a_{n-2}

设 $A_i=\left[\begin{matrix}a_i,a_{i+1}\end{matrix}\right]$

先构造 $1\times 2$ 的矩阵 $A_1=\left[\begin{matrix}a_1,a_2\end{matrix}\right]$ ，考虑构造矩阵 $B$ 使得 $A_1\times B=A_2$

通过观察推导得到 $B=\left[\begin{matrix}0&1\\1&1\end{matrix}\right]$

\begin{aligned} &\therefore A_2=A_1\times B\\ &\therefore A_3=A_2\times B=A_1\times B\times B=A_1\times B^2 \end{aligned}

\cdots

A_i=A_1\times B^{i-1}= \left[\begin{matrix}1,1\end{matrix}\right] \times \left[\begin{matrix} 0&1\\ 1&1\\ \end{matrix}\right]^{i-1}

时间复杂度： $\mathcal{O}(\log N)$

前置知识点

矩阵

定义：

矩阵加减

矩阵乘法

实现

单位矩阵

矩阵快速幂

快速幂

矩阵快速幂

本题题解

Preview: