【洛谷P1962】斐波那契数列

梦里梦外; 2023-06-05 08:52 26阅读 0赞

### Description ###

给定n，求斐波那契数列第n项对1e9+7取模的值

### Solution ###

由于数据太大，朴素的递推会超时，所以我们考虑用矩阵优化。

首先我们要明确矩阵乘法的运算法则，假设A是一个n\*m的矩阵，B是一个m\*p的矩阵，C是一个n\*p的矩阵且满足C=A\*B，那么存在

$$C\_\{i,j\}=\\sum\\limits\_\{k=1\}^\{m\}\{A\_\{i,k\}\*B\_\{k,j\}\}$$

举一个简单的例子就能直观的反映这个式子：

$$  
\\left\[  
\\begin\{matrix\}  
2 & 3 \\\\  
4 & 5  
\\end\{matrix\}  
\\right\] \\times  
\\left\[  
\\begin\{matrix\}  
6 \\\\  
7  
\\end\{matrix\}  
\\right\] =  
\\left\[  
\\begin\{matrix\}  
2\*6+3\*7 \\\\  
4\*6+5\*7  
\\end\{matrix\}  
\\right\]  
$$

然后我们考虑如何优化斐波那契数列

我们假设$Fib(n)$表示一个矩阵

$  
\\left\[  
\\begin\{matrix\}  
f\_\{n\} & f\_\{n-1\}  
\\end\{matrix\}  
\\right\]  
$，那么我们希望有一个矩阵base，使得$Fib(n-1)\\times base = Fib(n)$，也就是我们希望这样：

$$  
\\left\[  
\\begin\{matrix\}  
f\_\{n - 1\} & f\_\{n - 2\}  
\\end\{matrix\}  
\\right\] \\times base =  
\\left\[  
\\begin\{matrix\}  
f\_\{n\} & f\_\{n-1\}  
\\end\{matrix\}  
\\right\]$$

那么我们显然可以看出

$$base=\\left\[\\begin\{matrix\}1 & 1 \\\\1 & 0\\end\{matrix\}\\right\] $$

所以，我们定义初始矩阵$ans=\\left\[\\begin\{matrix\} f\_1 & f\_2\\end\{matrix\}\\right\] $*，*然后计算$ans\\times base^\{n-2\}$即可

关于计算结果，我们可以定义结构体并且重载乘号使得矩阵乘法可以直接运算，关于乘方运算我们可以类比整数快速幂来实现矩阵快速幂

时间复杂度为$O(2^3log\_2\{n\})$

### Code ###

![ContractedBlock.gif][] ![ExpandedBlockStart.gif][]

1 #include <bits/stdc++.h>
     2 using namespace std;
     3 const int mod = 1e9 + 7;
     4 typedef long long ll;
     5 ll n;
     6 struct Matrix {
     7     ll m[3][3];
     8     Matrix() {
     9         memset(m, 0, sizeof(m));
    10     }
    11     Matrix operator *(const Matrix &x) const {
    12         Matrix ret;
    13         for (register int i = 1; i <= 2; ++i)
    14             for (register int j = 1; j <= 2; ++j)
    15                 for (register int k = 1; k <= 2; ++k)
    16                     ret.m[i][j] = (ret.m[i][j] + m[i][k] * x.m[k][j]) % mod;
    17         return ret; 
    18     }
    19 } a, base;
    20 void qpow(ll p) {
    21     while (p) {
    22         if (p & 1) a = a * base;
    23         base = base * base;
    24         p >>= 1;
    25     }
    26 }
    27 int main() {
    28     scanf("%lld", &n);
    29     if (n <= 2) {
    30         puts("1");
    31         return 0;
    32     }
    33     base.m[1][1] = base.m[1][2] = base.m[2][1] = 1;
    34     a.m[1][1] = a.m[1][2] = 1;
    35     qpow(n - 2);
    36     printf("%lld\n", a.m[1][1] % mod);
    37     return 0;
    38 }

AC Code

转载于:https://www.cnblogs.com/shl-blog/p/11335378.html

[ContractedBlock.gif]: https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif
[ExpandedBlockStart.gif]: /images/20230601/c58fdda599634891b583f81714a6c76e.png