date: 2019-09-13
简介
标题看着很高端, 其实就是在 \(O(\log_2 N)\)内计算出线性递归数列的某一项(好像什么都没有解释清楚啊).
斐波那契数列的快速计算
我们先来看一个题目:
题目描述:
? 给你一个数字 \(n\), 你需要输出斐波那契数列的第 n 项.
? 注意: 第一项和第二项都为 \(1\).
题目输入:
? 第一行一个整数 \(n\), 保证 $1 \leq n \leq 1e18 $.
题目输出:
? 输出斐波那契数列的第 n 项, 对 \(1e9+7\)取模.
这道题目小数据范围内很简单 (一道水题), 但是当数据范围扩展到 \(1 \leq n \leq 1e18\) 时, 一切都不一样了. 你需要一个 \(O(N \log_2 N)\)的算法来解决它. 这里我们需要用到矩阵运算.
递推式
斐波那契数列的递推式这个大家应该都会写吧...
算了我还是来写一下好了:
\[ f_{i}=f_{i-1}+f_{i-2}\f_{0}=1\f_{1}=1 \]
转化为矩阵计算
这里我们把计算 \(f_0\)和 \(f_1\)包含在一个 2 行 1 列的矩阵中:
\[ \begin{pmatrix} f_{0}\f_{1} \end{pmatrix} \]
之后我们可以得出如下的式子:
\[ \begin{pmatrix} 0&1\1&1 \end{pmatrix} \begin{pmatrix} f_{0}\f_{1} \end{pmatrix} = \begin{pmatrix} f_{1}\f_{2} \end{pmatrix} \]
之后我们又可以得出如下的式子:
\[ \begin{pmatrix} 0&1\1&1 \end{pmatrix} ( \begin{pmatrix} 0&1\1&1 \end{pmatrix} \begin{pmatrix} f_{0}\f_{1} \end{pmatrix} ) = \begin{pmatrix} f_{2}\f_{3} \end{pmatrix} \]
由于矩阵的结合律, 我们又可以写成:
\[ \begin{pmatrix} 0&1\1&1 \end{pmatrix}^2 \begin{pmatrix} f_{0}\f_{1} \end{pmatrix} = \begin{pmatrix} f_{2}\f_{3} \end{pmatrix} \]
之后一步步递推, 就获得了:
\[ \begin{pmatrix} 0&1\1&1 \end{pmatrix}^n \begin{pmatrix} f_{0}\f_{1} \end{pmatrix} = \begin{pmatrix} f_{n}\f_{n+1} \end{pmatrix} \]
锵锵~ 我们就获得了一个复杂度大头是矩阵幂运算的递推式了. 众所周知, 由于结合律, 幂运算可以优化到 \(O(N\log_2 N)\), 这是可以接受的.
代码
- #include<bits/stdc++.h>
- using namespace std;
- typedef long long ll;
- const ll mod=1000000007;
- vector<vector<ll>> mul(const vector<vector<ll>> & a,const vector<vector<ll>> & b){
- vector<vector<ll>> res(2,vector<ll>(2,0));
- res[0][0]=(a[0][0]*b[0][0]+a[0][1]*b[1][0])%mod;
- res[0][1]=(a[0][0]*b[0][1]+a[0][1]*b[1][1])%mod;
- res[1][0]=(a[1][0]*b[0][0]+a[1][1]*b[1][0])%mod;
- res[1][1]=(a[1][0]*b[0][1]+a[1][1]*b[1][1])%mod;
- return res;
- }
- vector<vector<ll>> pow(vector<vector<ll>> a,ll n){
- vector<vector<ll>> res(2,vector<ll>(2,0));
- res[0][0]=1;
- res[1][1]=1;
- while(n>0){
- if(n&1){
- res=mul(res,a);
- }
- a=mul(a,a);
- n>>=1;
- }
- return res;
- }
- ll n;
- main(){
- iOS::sync_with_stdio(false);
- cin.tie(0);
- cout.tie(0);
- cin>>n;
- vector<vector<ll>> a(2,vector<ll>(2,1));
- a[0][0]=0;
- a=pow(a,n);
- cout<<a[0][1]<<endl;
- return 0;
- }
扩展至通用
递推式
直接上数学式:
\[ f_{i+M}=a_0f_{i}+a_1f_{i+1}+\cdots+a_{M-2}f_{i+M-2}+a_{M-1}f_{i+M-1} \]
矩阵计算
首先, 我们把这个数学式定义为一个 \(M\)行 \(1\)列的矩阵:
\[ \begin{pmatrix} f_i\f_{i+1}\f_{i+2}\\vdots\f_{i+M-2}\f_{i+M-1} \end{pmatrix} \]
之后, 递推式就可以这么写了:(\(a_k\)表示 \(f_{i+M}\)加上了 \(a_k f_{i+k}\))
\[ \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 & 0\0 & 0 & 1 & \cdots & 0 & 0\0 & 0 & 0 & \cdots & 0 & 0\\vdots & \vdots & \vdots & \ddots & \vdots & \vdots\0 & 0 & 0 & \cdots & 0 & 1\a_0 & a_1 & a_2 & \cdots & a_{M-2} & a_{M-1} \end{pmatrix} \begin{pmatrix} f_i\f_{i+1}\f_{i+2}\\vdots\f_{i+M-2}\f_{i+M-1} \end{pmatrix} = \begin{pmatrix} f_{i+1}\f_{i+2}\f_{i+3}\\vdots\f_{i+M-1}\f_{i+M} \end{pmatrix} \]
由于结合律, 递推式可以写成:
\[ \begin{pmatrix} 0 & 1 & 0 & \cdots & 0 & 0\0 & 0 & 1 & \cdots & 0 & 0\0 & 0 & 0 & \cdots & 0 & 0\\vdots & \vdots & \vdots & \ddots & \vdots & \vdots\0 & 0 & 0 & \cdots & 0 & 1\a_0 & a_1 & a_2 & \cdots & a_{M-2} & a_{M-1} \end{pmatrix}^n \begin{pmatrix} f_0\f_{1}\f_{2}\\vdots\f_{M-2}\f_{M-1} \end{pmatrix} = \begin{pmatrix} f_{n}\f_{n+1}\f_{n+2}\\vdots\f_{n+M-2}\f_{n+M-1} \end{pmatrix} \]
谢谢观看
帮忙在评论区里留下一些建设性言论帮助我们共同进步吧!
来源: http://www.bubuko.com/infodetail-3325877.html