传送门:

洛谷


Solution

这题我们显然不能直接递推,考虑用矩乘优化递推转移。

众所周知,f_i=f_{i-1}+f_{i-2}是斐波那契数列的转移方程,考虑将这个方程式写成矩阵形式。

很显然,将其写成1 \times 1的矩阵是极其不明智的决定,考虑到转移与前两项相关,那么我们将其写成1 \times 2的矩阵,如下所示:
\left[ \begin{matrix} f_i\\ f_{i-1} \end{matrix} \right]
我们考虑将转移过程用矩阵描述:
\left[ \begin{matrix} f_{i-1}\\ f_{i-2}\\ \end{matrix} \right] \to \left[ \begin{matrix} f_{i}\\ f_{i-1}\\ \end{matrix} \right] \\
我们变换一下形式:
\left[ \begin{matrix} f_{i-1}\\ f_{i-2}\\ \end{matrix} \right] \to \left[ \begin{matrix} 1 \times f_{i-1} + 1 \times f_{i-2}\\ 1 \times f_{i-1}\\ \end{matrix} \right]
那么我们就得到了转移过程中的辅助矩阵:
\left[ \begin{matrix} 1 & 1\\ 1 & 0\\ \end{matrix} \right]
那么很显然最终的答案就是:
\left[ \begin{matrix} 1 & 1\\ 1 & 0\\ \end{matrix} \right]^{n-2} \left[ \begin{matrix} f_2\\ f_1\\ \end{matrix} \right]
 于是我们只需要耗费O(\log_2 n)的时间去做一遍矩阵快速幂就好了。

Code

/*Program from Luvwgyx*/
#include<cstdio>
#include<cstring>
#include<algorithm>
#define int long long
#define write(x) printf("%lld\n",x)
using namespace std;
const int mod=1e9+7;
int read(){
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
struct Matrix{
    int a[3][3];
    Matrix(){memset(a,0,sizeof(a));}
    void init(){
        memset(a,0,sizeof(a));
        for(int i=1;i<3;i++)a[i][i]=1;
    }
}init;
Matrix mul(Matrix a,Matrix b){
    Matrix c;
    for(int i=1;i<3;i++)
        for(int j=1;j<3;j++)
            for(int k=1;k<3;k++)
                c.a[i][j]=(c.a[i][j]+1ll*a.a[i][k]*b.a[k][j]%mod)%mod;
    return c;
}
Matrix add(Matrix a,Matrix b){
    Matrix c;
    for(int i=1;i<3;i++)
        for(int j=1;j<3;j++)
            c.a[i][j]=(a.a[i][j]+b.a[i][j])%mod;
    return c;
}
Matrix power(Matrix a,int b){
    Matrix ret;ret.init();
    for(;b;b>>=1,a=mul(a,a))
        if(b&1)ret=mul(ret,a);
    return ret;
}
signed main(){
    init.a[1][1]=init.a[2][1]=1;
    Matrix now;now.a[1][1]=now.a[1][2]=now.a[2][1]=1;
    int n=read();if(n<=2){write(1ll);return 0;}
    write(mul(power(now,n-2),init).a[1][1]);
    return 0;
}

发表评论