date: 2019-09-13

简介

标题看着很高端,其实就是在\(O(\log_2 N)\)内计算出线性递归数列的某一项。

斐波那契数列的快速计算

我们先来看一个题目:

这道题目小数据范围内很简单,但是当数据范围扩展到\(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}\]

谢谢观看

帮忙在评论区里留下一些建设性言论帮助我们共同进步吧!

12-13 07:12
查看更多