• 欢迎光临~

AcWing 205. 斐波那契

开发技术 开发技术 2022-10-31 次浏览

(AcWing) (205). 斐波那契

题目传送门

一、题目描述

在斐波那契数列中,(F_ib_0=0,F_ib_1=1,F_ib_n=F_ib_{n−1}+F_ib_{n−2}(n>1))

给定整数 (n),求 (F_ib_n~ mod ~ 10000)

输入格式
输入包含多组测试用例。

每个测试用例占一行,包含一个整数 (n)

当输入用例 (n=−1) 时,表示输入终止,且该用例无需处理。

输出格式
每个测试用例输出一个整数表示结果。

每个结果占一行。

数据范围
(0≤n≤2×10^9)

二、矩阵乘法

(A)(P times M)的矩阵,(B)(M times Q) 的矩阵,设矩阵 (C) 为矩阵 (A)(B) 的乘积,

其中矩阵 (C) 中的第 (i) 行第 (j) 列元素可以表示为:

[large C_{i,j} = sum_{k=1}^MA_{i,k}B_{k,j} ]

如果没看懂上面的式子,没关系。通俗的讲,在矩阵乘法中,结果 (C) 矩阵的第 (i) 行第 (j) 列的数,就是由矩阵 (A)(i)(M) 个数与矩阵 (B)(j)(M) 个数分别 ①相乘②相加 得到的。

三、本题题解

斐波那契数列((Fibonacci) (Sequence))大家应该都非常的熟悉了。在斐波那契数列当中,

[large F_1 = F_2 = 1,F_i = F_{i - 1} + F_{i - 2}~(i geq 3) ]

如果有一道题目让你求斐波那契数列第 (n) 项的值,最简单的方法 莫过于直接 递推。但是如果 (n) 的范围达到了 (10^{9})级别,递推就不行了,稳稳 (TLE), 考虑 矩阵加速递推:

(Fib(n)) 表示一个 (1 times 2) 的矩阵 (left[begin{array}{ccc}F_n & F_{n-1} end{array}right])。我们 希望 根据 (Fib(n-1)=left[ begin{array}{ccc}F_{n-1} & F_{n-2} end{array}right]) 经过一些变换,推出 (Fib(n))

(Q:)怎么推呢?

  • ① 试推导一个矩阵 (base),使 (Fib(n-1) times text{base} = Fib(n)),即

[large left[begin{array}{ccc}F_{n-1} & F_{n-2}end{array}right] times text{base} = left[ begin{array}{ccc}F_n & F_{n-1} end{array}right] ]

因为 (F_n=F_{n-1}+F_{n-2}),所以 (base) 矩阵第一列应该是 (left[begin{array}{ccc} 1 \ 1 end{array}right]),这样在进行矩阵乘法运算的时候才能令 (F_{n-1})(F_{n-2}) 相加,从而得出 (F_n)。同理,为了得出 (F_{n-1}),矩阵 (base) 的第二列应该为 (left[begin{array}{ccc} 1 \ 0 end{array}right])

综上所述:(text{base} = left[begin{array}{ccc} 1 & 1 \ 1 & 0 end{array}right]) ,原式化为

[large left[begin{array}{ccc}F_{n-1} & F_{n-2}end{array}right] times left[begin{array}{ccc} 1 & 1 \ 1 & 0 end{array}right] = left[ begin{array}{ccc}F_n & F_{n-1} end{array}right] ]

  • ② 转化为代码,应该怎么求呢?

定义初始矩阵 (text{ans} = left[begin{array}{ccc}F_2 & F_1end{array}right] = left[begin{array}{ccc}1 & 1end{array}right], text{base} = left[begin{array}{ccc} 1 & 1 \ 1 & 0 end{array}right])。那么,(F_n)
​就等于 (text{ans} times text{base}^{n-2}), 这个矩阵的第一行第一列元素,也就是 (left[begin{array}{ccc}1 & 1end{array}right] times left[begin{array}{ccc} 1 & 1 \ 1 & 0 end{array}right]^{n-2}) 的第一行第一列元素。

注意
矩阵乘法不满足交换律,所以一定不能写成 (left[begin{array}{ccc} 1 & 1 \ 1 & 0 end{array}right]^{n-2} times left[begin{array}{ccc}1 & 1end{array}right]) 的第一行第一列元素。

  • 对于 (n leq 2) 的情况,直接输出 (1) 即可,不需要执行矩阵快速幂。

  • 为什么要乘上 (base) 矩阵的 (n-2) 次方而不是 (n) 次方呢?因为 (F_1, F_2) 是不需要进行矩阵乘法就能求的。也就是说,如果只进行一次乘法,就已经求出 (F_3)了。如果还不是很理解为什么幂是 (n-2),建议手算一下。

四、实现代码

#include <bits/stdc++.h>
using namespace std;
const int N = 10; //这个黄海实测,写成3也可以AC,考虑到矩阵乘法的维度,一般写成10,差不多的都可以过掉
const int MOD = 10000;

int base[N][N], res[N][N];
int t[N][N];

//矩阵乘法,为快速幂提供支撑
inline void mul(int C[][N], int A[][N], int B[][N]) {
    memset(t, 0, sizeof t);
    for (int k = 1; k <= 2; k++)
        for (int i = 1; i <= 2; i++)
            for (int j = 1; j <= 2; j++)
                t[i][j] = (t[i][j] + (A[i][k] * B[k][j]) % MOD) % MOD;
    memcpy(C, t, sizeof t);
}

//快速幂
void qmi(int k) {
    memset(res, 0, sizeof res);
    res[1][1] = res[1][2] = 1; //结果是一个横着走,一行两列的矩阵
                               // P * M 与 M * Q 的矩阵才能做矩阵乘积,背下来即可
    //矩阵快速幂,就是乘k次 base矩阵,将结果保存到res中
    //本质上就是利用二进制+log_2N的特点进行优化
    while (k) {
        //比如 1101
        if (k & 1) mul(res, res, base); // res=res*b
        mul(base, base, base);          //上一轮的翻番base*=base
        k >>= 1;                        //不断右移
    }
}

int main() {
    int n;
    while (cin >> n) {
        if (n == -1) break;
        if (n == 0) {
            puts("0");
            continue;
        }
        if (n <= 2) {
            puts("1");
            continue;
        }

        // base矩阵
        memset(base, 0, sizeof base);
        /**
         1 1
         1 0

         第一行第一列为1
         第一行第二列为1
         第二行第一列为1
         第二行第二列为0 不需要设置,默认值
        */
        base[1][1] = base[1][2] = base[2][1] = 1;

        //快速幂
        qmi(n - 2);

        //结果
        printf("%dn", res[1][1]);
    }

    return 0;
}

程序员灯塔
转载请注明原文链接:AcWing 205. 斐波那契
喜欢 (0)