在次线性时间内计算线性递归数列

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} \]

谢谢观看

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

在次线性时间内计算线性递归数列

原文：https://www.cnblogs.com/BlahDuckling747/p/12019569.html