M_sea

洛谷1962 斐波那契数列
Luogu算法递推即可。然而$n$过大,需要矩阵加速。考虑矩阵$A=(f[i-1],f[i-2])$。我们要让它在...
扫描右侧二维码阅读全文
02
2018/08

洛谷1962 斐波那契数列

Luogu

算法

递推即可。

然而$n$过大,需要矩阵加速。

考虑矩阵$A=(f[i-1],f[i-2])$。

我们要让它在一次矩乘后变成$A'=(f[i],f[i-1])$。

事实上有:$f[i]=f[i-1]*1+f[i-2]*1$,$f[i-1]=f[i-2]*0+f[i-1]*1$。

那么构造出矩阵转移矩阵$\begin{vmatrix}1&1\\1&0\end{vmatrix}$

矩阵快速幂搞搞即可。

记得开long long

细节见代码。

代码

#include <bits/stdc++.h>
#define re register
typedef int mainint;
#define int long long
using namespace std;

const int MOD=1e9+7; 

struct Matrix {
    int x,y;
    int m[10][10];
};

Matrix Mul(Matrix a,Matrix b) {
    Matrix c; c.x=a.x,c.y=b.y;
    for (re int i=1;i<=a.x;i++)
        for (re int j=1;j<=b.y;j++) {
            c.m[i][j]=0;
            for (re int k=1;k<=a.y;k++)
                c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%MOD;
        }
    return c;
}

Matrix FastPow(Matrix a,int k) {
    Matrix rt;
    rt.x=rt.y=a.x;
    for (re int i=1;i<=a.x;i++) //构造单位矩阵 
        for (re int j=1;j<=a.y;j++)
            rt.m[i][j]=(i==j);
    while (k) {
        if (k&1) rt=Mul(rt,a);
        a=Mul(a,a);
        k>>=1;
    }
    return rt;
}

mainint main() {
    int S; scanf("%lld",&S);
    if (S<=2) { printf("1\n"); return 0; }
    Matrix A,B;
    
    A.x=1,A.y=2,B.x=2,B.y=2;
    A.m[1][1]=A.m[1][2]=1;
    B.m[1][1]=B.m[1][2]=B.m[2][1]=1;
    B.m[2][2]=0;
    
    A=Mul(A,FastPow(B,S-2));
    printf("%lld\n",A.m[1][1]);
    return 0;
}
最后修改:2018 年 12 月 01 日 03 : 30 PM

发表评论