当前位置: 首页 > article >正文

洛谷 P1962:斐波那契数列 ← 矩阵快速幂

【题目来源】
https://www.luogu.com.cn/problem/P1962

【题目描述】
大家都知道,斐波那契数列是满足如下性质的一个数列:F1=1,F2=1,Fn=Fn-1+Fn-2,n≥3。
请你求出 Fn​ mod
10^9+7 的值。

【输入格式】
一行一个正整数 n。

【输出格式】
输出一行一个整数表示答案。


【输入样例】
10

【输出样例】
55

【数据范围】
对于 60% 的数据,1≤n≤92;
对于 100% 的数据,1≤n<2^63。


【算法分析】


【算法代码】

#include<bits/stdc++.h>
using namespace std;

typedef long long LL;
const int maxn=2;
const int MOD=1e9+7;
LL n;

struct Matrix {
    LL m[maxn][maxn];
    Matrix() { //Constructor in struct
        memset(m,0,sizeof m);
    }
};

Matrix mul(Matrix a, Matrix b) {
    Matrix ans;
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                ans.m[i][j]=(ans.m[i][j]+a.m[i][k]*b.m[k][j])%MOD;
    return ans;
}

void fastPow(LL n) {
    Matrix base,t;
    base.m[0][0]=1,base.m[0][1]=1;
    base.m[1][0]=1,base.m[1][1]=0;
    t.m[0][0]=1,t.m[0][1]=1; //f[1]=1,f[2]=1

    while(n) {
        if(n&1) t=mul(t,base);
        base=mul(base,base);
        n=n>>1;
    }
    cout<<t.m[0][0]<<endl;
}

int main() {
    cin>>n;
    if(n==1) cout<<"1"<<endl;
    else fastPow(n-2);

    return 0;
}

/*
in:
10

out:
55
*/



【参考文献】
https://blog.csdn.net/hnjzsyjyj/article/details/143227091
https://mp.weixin.qq.com/s/Az68VdFnRDUZ8vczKwRB4g
https://www.cnblogs.com/zxsoul/articles/14407155.html

 


http://www.kler.cn/a/587124.html

相关文章:

  • [人工智能]实现神经网络实例
  • 04.Python基础3
  • go~大型项目的参数注册
  • [local-file-system]基于服务器磁盘的本地文件存储方案
  • CentOS 系统安装 docker 以及常用插件
  • Elasticsearch分页查询、关键词高亮与性能优化全解析
  • 国产芯片替代方案:解析沁恒以太网控制器芯片,内置MAC地址
  • 【MySQL】undo日志类型
  • CSS3学习教程,从入门到精通,CSS3 选择器权重问题语法知识点及案例代码(5)
  • Freertos--把队列加入队列集
  • 使用tiptap快速搭建markdown-富文本编辑器
  • 电路基础【2】:三极管基础:PNP与NPN三极管详解
  • FPGA 中 assign 和 always 区别
  • 2.4滑动窗口专题:将 x 减到 0 的最小操作数
  • 均方误差(MSE)与最小二乘法(LS)的区别
  • 数字孪生像魔镜,映照出无限可能的未来
  • 二进制数(十进制转二进制)
  • 标定棋盘格大小的选择
  • 车载Android音频系统 CarAudioService
  • React 常用 Hooks 详细解析