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

lanqiaoOJ 1180:斐波那契数列 ← 矩阵快速幂

【题目来源】
https://www.lanqiao.cn/problems/1180/learning/

【题目描述】
定义斐波那契数列数列为 F1=1,F2=1,Fn=Fn-1+Fn-2,n>2。
给定一个正整数 n,求 Fn 在模
10^9+7 的值。

【输入格式】
第1行为一个整数 T,表示测试数据数量。
接下来的 T 行每行包含一个正整数 N。
1≤T≤10^4,1≤N≤
10^18

【输出格式】
输出共 T 行,每行包含一个整数,表示答案。

【输入样例】
6
1
2
3
4
5
1000000000

【输出样例】
1
1
2
3
5
21

【算法分析】
本题(lanqiaoOJ 1180)与洛谷 P1962 的分析思路一样。

【算法代码】

#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[2]=1,f[1]=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() {
    int T;
    cin>>T;
    while(T--) {
        cin>>n;
        if(n==1) cout<<"1"<<endl;
        else fastPow(n-2);
    }

    return 0;
}

/*
in:
6
1
2
3
4
5
1000000000

out:
1
1
2
3
5
21
*/



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


 

原文地址:https://blog.csdn.net/hnjzsyjyj/article/details/146273704
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.kler.cn/a/586853.html

相关文章:

  • 找工作、创业的思考和出路
  • JVM之工具篇
  • 华为手机助手输入连接码时光标乱跳
  • 数据结构(C\C++)——算法复杂度
  • Django 分页操作详解
  • 【CodeMirror】系列(一)官网文档学习(二)核心扩展列表
  • Jetson Nano NX 重装系统
  • CSS3学习教程,从入门到精通, CSS3入门介绍的语法知识点及案例(1)
  • ssh通过22端口无法连接服务器问题处理
  • Python----数据可视化(Pyecharts三:绘图二:涟漪散点图,K线图,漏斗图,雷达图,词云图,地图,柱状图折线图组合,时间线轮廓图)
  • Java方法继承、方法重载、方法覆盖总结
  • Hive SQL 精进系列: IF 函数的强大功能与高级应用
  • Qlik Sense New Install with Restore
  • 【PlatformIO】基于Arduino的ESP8266 锂电池电压、电量测试
  • 射频前端模块(FEM)的基本原理与架构:从组成到WiFi路由器的应用
  • 1、操作系统引论
  • C语言 | 二叉树打印效果,控制台打印
  • 【Git学习笔记】Git初识及其结构原理分析(一)
  • JavaScript性能优化的几个方面入手
  • matlab 谐波分析公式绘图