洛谷 – P1962 – 斐波那契数列

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;
}

单位矩阵

形如:

$$
\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;
}

矩阵快速幂

利用快速幂思想,快速求矩阵$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;
}

本题题解

斐波那契数列递推式:

$$
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)$

暂无评论

发送评论 编辑评论

|´・ω・)ノ
ヾ(≧∇≦*)ゝ
(☆ω☆)
(╯‵□′)╯︵┴─┴
 ̄﹃ ̄
(/ω\)
∠( ᐛ 」∠)_
(๑•̀ㅁ•́ฅ)
→_→
୧(๑•̀⌄•́๑)૭
٩(ˊᗜˋ*)و
(ノ°ο°)ノ
(´இ皿இ`)
⌇●﹏●⌇
(ฅ´ω`ฅ)
(╯°A°)╯︵○○○
φ( ̄∇ ̄o)
ヾ(´・ ・`。)ノ"
( ง ᵒ̌皿ᵒ̌)ง⁼³₌₃
(ó﹏ò。)
Σ(っ °Д °;)っ
( ,,´・ω・)ノ"(´っω・`。)
╮(╯▽╰)╭
o(*////▽////*)q
>﹏<
( ๑´•ω•) "(ㆆᴗㆆ)
😂
😀
😅
😊
🙂
🙃
😌
😍
😘
😜
😝
😏
😒
🙄
😳
😡
😔
😫
😱
😭
💩
👻
🙌
🖕
👍
👫
👬
👭
🌚
🌝
🙈
💊
😶
🙏
🍦
🍉
😣
Source: github.com/k4yt3x/flowerhd
颜文字
Emoji
小恐龙
花!
上一篇
下一篇