首页 > > 程序设计 > C/C++ >

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

2018-06-17 20:59:41来源：未知阅读 ()

题目背景

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

• 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：复制

输出样例#1：复制

输入样例#2：复制

输出样例#2：复制

说明

对于 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=101;
const int mod=1e9+7;
char buf[1<<20],*p1=buf,*p2=buf;
inline int read()
{
    char c=getchar();int x=0,f=1;
    while(c<'0'||c>'9'){if(c=='-')f=-1;c=getchar();}
    while(c>='0'&&c<='9'){x=x*10+c-'0';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=1;k<=n;k++)
            for(int i=1;i<=n;i++)
                for(int j=1;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=1;i<=n;i++) ans.m[i][i]=1;
        while(p)
        {
            if(p&1) ans=ans*a;
            a=a*a;
        //    a.print();
            p>>=1;
        }
        return ans;
    }
    void print()
    {
        for(int i=1;i<=n;i++,puts(""))
            for(int j=1;j<=n;j++)
                printf("%d ",m[i][j]);
        printf("*******************\n");
    }
};
main()
{
    #ifdef WIN32
    freopen("a.in","r",stdin);
    #endif
    k=read();n=2;
    Matrix temp,ans;
    temp.m[1][1]=0;temp.m[1][2]=1;
    temp.m[2][1]=1;temp.m[2][2]=1;
    ans.m[1][1]=0;ans.m[1][2]=1;
    ans.m[2][1]=0;ans.m[2][2]=1;
    temp=temp.pow(k);
    ans=ans*temp;
    printf("%d",ans.m[1][1]);
    return 0;
}