洛谷P1962 斐波那契数列(矩阵快速幂)

时间：2021-03-29 19:27:15

题目背景

大家都知道，斐波那契数列是满足如下性质的一个数列：

• f(1) = 1

• f(2) = 1

• f(n) = f(n-1) + f(n-2) (n ≥ 2 且 n 为整数)

题目描述

请你求出 f(n) mod 1000000007 的值。

输入输出格式

输入格式：

·第 1 行：一个整数 n

输出格式：

第 1 行： f(n) mod 1000000007 的值

输入输出样例

输入样例#1： 复制 
5
输出样例#1： 复制 
5
输入样例#2： 复制 
10
输出样例#2： 复制 
55

说明

对于 60% 的数据： n ≤ 92

对于 100% 的数据： n在long long(INT64)范围内。

感觉自己学的一直是假的矩阵快速幂。。。

辅助矩阵为

$\begin{bmatrix} 0 & 1 \\ 1 & 1 \end{bmatrix}$

#include<cstdio>

#include<cstring>

#define int long long

#define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,MAXN,stdin),p1==p2)?EOF:*p1++)

using namespace std;

const int MAXN=;

const int mod=1e9+;

char buf[<<],*p1=buf,*p2=buf;

inline int read()

{

    char c=getchar();int x=,f=;

    while(c<''||c>''){if(c=='-')f=-;c=getchar();}

    while(c>=''&&c<=''){x=x*+c-'';c=getchar();}

    return x*f;

}

int n,k;

struct Matrix

{

    int m[MAXN][MAXN];

    Matrix operator * (const Matrix a)const

    {

        Matrix ans={};

        for(int k=;k<=n;k++)

            for(int i=;i<=n;i++)

                for(int j=;j<=n;j++)

                    ans.m[i][j]=(ans.m[i][j]+(m[i][k]*a.m[k][j])%mod)%mod;

        return ans;

    }

    Matrix pow(int p)

    {

        Matrix ans,a=(*this);

        for(int i=;i<=n;i++) ans.m[i][i]=;

        while(p)

        {

            if(p&) ans=ans*a;

            a=a*a;

        //    a.print();

            p>>=;

        }

        return ans;

    }

    void print()

    {

        for(int i=;i<=n;i++,puts(""))

            for(int j=;j<=n;j++)

                printf("%d ",m[i][j]);

        printf("*******************\n");

    }

};

main()

{

    #ifdef WIN32

    freopen("a.in","r",stdin);

    #endif

    k=read();n=;

    Matrix temp,ans;

    temp.m[][]=;temp.m[][]=;

    temp.m[][]=;temp.m[][]=;

    ans.m[][]=;ans.m[][]=;

    ans.m[][]=;ans.m[][]=;

    temp=temp.pow(k);

    ans=ans*temp;

    printf("%d",ans.m[][]);

    return ;

}

相关文章