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

题目背景

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

• 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=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;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏吴伟祥

认识XPath(确定XML文档中某部分位置的语言)

XPath即为XML路径语言(XML Path Language),它是一种用来确定XML文档中某部分位置的语言。

8810
来自专栏landv

c语言_头文件

21930
来自专栏V站

PHP把二维数组中的值取出组合整一维数组

小伙伴们,之前我们在开发过程中肯定遇到需要把二维数组转换为一维数组的时候,基本上都运用了foreach循环遍历赋值给新数组. 今天这里介绍一个新的方法,通过两个...

20520
来自专栏小樱的经验随笔

洛谷P1313 计算系数【快速幂+dp】

P1313 计算系数 题目描述 给定一个多项式(by+ax)^k,请求出多项式展开后x^n*y^m 项的系数。 输入输出格式 输入格式: 输入文件名为facto...

22650
来自专栏Java爬坑系列

C\C++ 生成各位数不相等的随机数

  最近想写一个1A2B的小游戏来练习一下,结果在第一步生成随机数的时候就遇到了一点点问题。   游戏初始化时需要先生成一个四位随机数,且各位各不相等。于是最开...

28570
来自专栏西枫里博客

单数据和批量数据的删除操作

通常对某条数据的删除和某一批数据的删除分别采用两个成员方法。这样太累赘了一些,为了使用批量删除的成员方法,就需要构造单数据的结构。这里以ID为数组作为例子

9930
来自专栏数据结构与算法

51nod1004 n^n的末位数字

题目来源: Author Ignatius.L (Hdu 1061) 基准时间限制:1 秒 空间限制:131072 KB 分值: 5  难度:1级算法题 给出一...

35960
来自专栏Hongten

python开发_random

和java中的random()函数一样,在python中也有类似的模块random,即随机数

11420
来自专栏数据结构与算法

cf1028C. Rectangles(前缀和)

呵呵哒,昨天cf半夜场,一道全场切的题,我没做出来。。不想找什么理由,不会做就是不会做。。

7830
来自专栏算法与数据结构

PTA 数据结构 一元多项式求导 (仅供参考)

请勿粘贴 输入格式: 以指数递降方式输入多项式非零项系数和指数(绝对值均为不超过1000的整数)。数字间以空格分隔。 输出格式: 以与输入相同的格式输出导数多项...

229100

扫码关注云+社区

领取腾讯云代金券