斐波那契数列矩阵乘法优化DP

求$f(n) \%1000000007$，$n\le 10^{18}$

矩阵乘法：$i\times k$的矩阵$A$乘$k\times j$的矩阵$B$得到$k\times k$的矩阵，其中第$i$列第$j$行的数就是$A$的第$i$行所有数与$B$的第$j$列分别相乘再相加

考虑使用矩阵乘法优化DP，为了最后得到$f(n)$，我们设矩阵$\text{base}$，使$\begin{bmatrix} F_{n-1} & F_{n-2} \end{bmatrix} \times base = \begin{bmatrix} F_{n} & F_{n-1} \end{bmatrix}$，容易推得得$base=\begin{bmatrix} 1 & 1 \\ 1 & 0 \end{bmatrix}$

然后因为矩阵乘法可以使用快速幂优化，所以我们直接算出$base^{n-2}$，答案即为$\begin{bmatrix} 1 & 1 \end{bmatrix} \times base^{n-2} $矩阵的第一行第一列

#include <cstdio>

#include <cstring>

#define MOD 1000000007

using namespace std;

long long n;

struct Mat{

    long long a[3][3];

    Mat(){memset(a, 0, sizeof a);}

    Mat operator * (const Mat &b) const{

        Mat res;

        for(int i=1;i<=2;++i)

            for(int j=1;j<=2;++j)

                for(int k=1;k<=2;++k)

                    res.a[i][j]=(res.a[i][j] + (a[i][k] * b.a[k][j])%MOD)%MOD;

        return res;

    }

} ans, base;

void qpow(long long x){

    while(x!=0){

        if(x&1) ans=ans*base;

        x>>=1;

        base=base*base;

    }

}

int main(){

    scanf("%lld", &n);

    if(n<=2){

        puts("1");

        return 0;

    }

    ans.a[1][1]=ans.a[1][2]=1;

    base.a[1][1]=1,base.a[1][2]=1,base.a[2][1]=1,base.a[2][2]=0;

    qpow(n-2);

    printf("%lld", ans.a[1][1]);

    return 0;

}

巴特西

斐波那契数列矩阵乘法优化DP

斐波那契数列矩阵乘法优化DP

最新文章

热门文章

巴特西

斐波那契数列 矩阵乘法优化DP

斐波那契数列 矩阵乘法优化DP

最新文章

热门文章

斐波那契数列矩阵乘法优化DP

斐波那契数列矩阵乘法优化DP