蓝桥集训之斐波那契数列

蓝桥集训之斐波那契数列

  • 核心思想:矩阵乘法

    • 将原本O(n)的递推算法优化为O(log2n)

    • 在这里插入图片描述

    • 构造1x2矩阵f和2x2矩阵a

    • 发现f(n+1) = f(n) * a

      • 则f(n+1) = f(1) * an
      • 可以用快速幂优化
  •   #include <iostream>
      #include <cstring>
      #include <algorithm>
      
      using namespace std;
      const int MOD = 10000;
      int f[2];
      int a[2][2];
      int n;
      
      void mul1()
      {
          int res[2];  //res = res*a 求1x2矩阵
          memset(res,0,sizeof res);
          for(int i=0;i<2;i++)
              for(int j=0;j<2;j++)
                  res[i] = (res[i] + f[j] * a[j][i]) %MOD;  //计算f*a
                  
          memcpy(f,res,sizeof f);
      }
      void mul2()
      {
          int res[2][2];  //a = a*a 求2x2矩阵
          memset(res,0,sizeof res);
          for(int i=0;i<2;i++)
              for(int j=0;j<2;j++)
                  for(int k=0;k<2;k++)
                      res[i][j] = (res[i][j] + a[i][k] * a[k][j])%MOD;  //计算a*a
          
          memcpy(a,res,sizeof a);
      }
      void qmi(int n)
      {
          while (n)  //快速幂优化
          { 
              if(n&1) mul1();  //res = res*a%MOD
              mul2();  //a = a*a%MOD
              n>>=1;
          }
      }
      int main()
      {
          while(cin>>n , n!=-1)
          {
              f[0] = 0,f[1] = 1;  //初始化第0 1项
              a[0][0] = 0,a[0][1] = 1,a[1][0] = 1,a[1][1] = 1;  //初始化a矩阵
              qmi(n); 
              cout<<f[0]<<endl;
          }
          return 0;
      }
    

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:/a/519904.html

如若内容造成侵权/违法违规/事实不符,请联系我们进行投诉反馈qq邮箱809451989@qq.com,一经查实,立即删除!

相关文章

ES13 学习

文章目录 1. 私有属性和方法静态代码块 2. 最外层的await3. at 函数4. 正则匹配的开始和结束索引5. findLast() 和findLastIndex()6. Error 对象的Cause 属性 1. 私有属性和方法 ES13 的改进之处&#xff1a; 创建对象时&#xff0c;如果有不需要外界传参进来的属性&#xff…

PCIe 7.0|不要太卷,劝你先躺平

PCIe 6.0都已经发布了2-3年了&#xff0c;目前业内生态还没完全建立。甚至很多人都还没用上PCIe 5.0呢&#xff01; 近日&#xff0c;PCIe 7.0 ver0.5版本已经开放&#xff0c;同时宣布马不停蹄准备在2025年完成正式SPEC规范发布。 回顾PCIe 7.0变更&#xff0c;PCI-SIG在2022年…

Google视觉机器人超级汇总:从RT、RT-2到AutoRT、SARA-RT、RT-Trajectory

前言 随着对视觉语言机器人研究的深入&#xff0c;发现Google的工作很值得深挖&#xff0c;比如RT-2 ​想到很多工作都是站在Google的肩上做产品和应用&#xff0c;​Google真是科技进步的核心推动力&#xff0c;做了大量大模型的基础设施&#xff0c;服 故有了本文&#xf…

从概念到实践:探索独立站在当代电商中的关键作用

随着数字化时代的到来&#xff0c;电子商务已成为全球商业生态的核心组成部分。在这个不断变化的市场中&#xff0c;独立站作为企业建立在线身份和拓展业务的强大工具&#xff0c;正逐步展现出其不可替代的价值。 从概念到实践&#xff0c;本文将深入探索独立站在当代电商中的关…

C语言中strcpy函数的实现

C语言中strcpy函数的实现 为了便于和strcpy函数区别&#xff0c;以下命令为_strcpy。 描述&#xff1a;实现strcpy&#xff0c;字符串拷贝函数&#xff0c;函数原型如下&#xff1a; char* strcpy(char* _Destination, const char *_Source);_strcpy实现&#xff1a; char*…

01-​JVM学习记录-类加载器

一、类加载器子系统 1. 作用-运输工具&#xff08;快递员&#xff09; 负责从文件系统或者网络中加载Class文件&#xff08;DNA元数据模板&#xff09;&#xff0c;Class文件开头有特定标识&#xff0c;魔术&#xff0c;咖啡杯壁&#xff08;class文件存于本地硬盘&#xff0c…

169.乐理基础-调式板块总结、调式判断

如果到这五线谱还没记住还不认识的话去看102.五线谱-高音谱号与103.五线谱-低音谱号这两个里&#xff0c;这里面有五线谱对应的音名&#xff0c;对比着看 如果不认识调号去看112.五线谱的调号&#xff08;一&#xff09;、113.五线谱的调号&#xff08;二&#xff09;、114.快…

华为激光雷达真的遥遥领先吗?华为激光雷达详细拆解和系统方案分析(55图)

华为作为中国自动驾驶技术第一梯队的卓越代表&#xff0c;其激光雷达产品也备受瞩目&#xff0c;不过关于华为激光雷达的公开资料非常少&#xff0c;即便是有也非常粗略。 本文通过详细拆解华为96线激光雷达产品&#xff0c;尝试分析华为激光雷达的技术方案&#xff0c;并通过…

提取word文档里面的图片

大家好&#xff0c;我是阿赵。   阿赵我写博客的时候的习惯是&#xff0c;先用word文档写好&#xff0c;然后再把word文档里面的图片另存&#xff0c;最后再在博客里面复制正文和上传图片。   而我写的文章一般配图都比较多&#xff0c;所以经常要做的一个功能就是另存图片…

Kubernetes 高可用性入门:初学者指南

Kubernetes 高可用性解释 引言一、需要 Kubernetes 高可用性二、Kubernetes 控制平面的高可用性2.1、etcd2.2、API 服务器2.3、Kube 调度器2.4、Kube 控制器管理器2.5、云控制器管理器 三、工作节点的高可用性四、Kubernetes 集群可用性度量五、Kubernetes 可用性常见问题六、总…

基于java 的高校设备管理系统

摘要 高校是培养人才的重要场所&#xff0c;拥有大量的设备和器材&#xff0c;如实验室设备、学生宿舍设备、教学设备等&#xff0c;这些设备的管理对于高校事业的顺利发展起着至关重要的作用。随着高校信息化建设的不断深入&#xff0c;高校设备管理已逐渐成为学院日常教学环…

蓝鲸6.1 CMDB 事件推送的开源替代方案

本文来自腾讯蓝鲸智云社区用户&#xff1a;木讷大叔爱运维 背景 在蓝鲸社区“社区问答”帖子中发现这么一个需求&#xff1a; 究其原因&#xff0c;我在《不是CMDB筑高墙&#xff0c;运维需要一定的开发能力&#xff01;》一文中已经介绍&#xff0c;在此我再简单重复下&#…

Apache Pulsar源码解析之Lookup机制

引言 在学习Pulsar一段时间后&#xff0c;相信大家也或多或少听说Lookup这个词&#xff0c;今天就一起来深入剖析下Pulsar是怎么设计的它吧 Lookup是什么 在客户端跟服务端建立TCP连接前有些信息需要提前获取&#xff0c;这个获取方式就是Lookup机制。所获取的信息有以下几种…

[机器学习]人工智能为小米智架保驾护航

前言 小米汽车作为小米集团进军汽车行业的新尝试&#xff0c;吸引了广泛的关注。其结合了小米在科技和创新方面的优势&#xff0c;以及对智能出行的愿景&#xff0c;为汽车行业注入了新的活力。虽然小米汽车工厂还处于初期阶段&#xff0c;但其积极采用人工智能和机器学习等前沿…

基于Pytorch+昇腾NPU部署baichuan2-7B大模型

一、模型介绍 Baichuan 2 是百川智能推出的新一代开源大语言模型&#xff0c;采用 2.6 万亿 Tokens 的高质量语料训练。Baichuan 2 在多个权威的中文、英文和多语言的通用、领域 benchmark 上取得同尺寸最佳的效果。 它基于 Transformer 结构&#xff0c;在大约1.2万亿 tokens…

docker进行jenkins接口自动化测试持续集成实战

文章目录 一、接口功能自动化测试项目源码讲解二、接口功能自动化测试运行环境配置1、下载jdk&#xff0c;maven&#xff0c;git&#xff0c;allure并配置对应的环境变量2、使用docker安装jenkins3、配置接口测试的运行时环境选择对应节点4、jenkins下载插件5、jenkins配置环境…

解决element-plus table组件 fixed=“right“(left)浮动后横向滚动文字穿透的问题

BUG 版本&#xff1a;element-plus 2.6.1 浏览器&#xff1a;360极速浏览器22.1 (Chromium内核) 组件&#xff1a;el-table组件 问题&#xff1a;在头部/尾部浮动加上斑马条纹后&#xff0c;横向滚动存在文字穿透的问题。具体如图&#xff1a; 白色背景行的文字&#xff0c…

【关于窗口移动求和的两种计算方法】

窗口移动计算方法 例子方法1方法2运行结果: 例子 在很多算法中都会涉及到窗口滑动&#xff0c;比如基于新息序列更新的自适应卡尔曼滤波器算法中便会使用到。 已知一个数列&#xff1a;OCV [1;2;3;4;5;6;7;8;9;10;11;12;13;14;15]&#xff0c;定义窗口长度为5&#xff0c;每次…

Python自带的集成开发和学习环境IDLE 中安装工具包的pip文件修复和重置解决方法————以win 7系统下Python 3.8 32-bit为例

Python自带的集成开发和学习环境IDLE 中安装工具包的pip文件修复和重置解决方法————以win 7系统下Python 3.8 32-bit为例 目录 Python自带的集成开发和学习环境IDLE 中安装工具包的pip文件修复和重置解决方法————以win 7系统下Python 3.8 32-bit为例一、IDLE简介和特点…

软考111-上午题-【计算机网络】-URL和DNS

一、URL解析 org&#xff1a;各类组织结构&#xff08;非盈利团队&#xff09; 1-1、顶级域 顶级域名是域名的最后一个部分&#xff0c;即是域名最后一点之后的字母&#xff0c;例如&#xff1a;www.baidu.com这个域名中&#xff0c;顶级域是.com&#xff08;或.COM&#xff…