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

蓝桥集训之斐波那契数列

蓝桥集训之斐波那契数列

  • 核心思想:矩阵乘法

    • 将原本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*amemcpy(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*amemcpy(a,res,sizeof a);}void qmi(int n){while (n)  //快速幂优化{ if(n&1) mul1();  //res = res*a%MODmul2();  //a = a*a%MODn>>=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;}
    

相关文章:

蓝桥集训之斐波那契数列

蓝桥集训之斐波那契数列 核心思想&#xff1a;矩阵乘法 将原本O(n)的递推算法优化为O(log2n) 构造1x2矩阵f和2x2矩阵a 发现f(n1) f(n) * a 则f(n1) f(1) * an可以用快速幂优化 #include <iostream>#include <cstring>#include <algorithm>using na…...

程序员的工资是多少,和曹操有莫大的关系

曹操是谁大家都知道了吧&#xff0c;他是三国时期的一个有名的大老板&#xff0c;谁知道曹操的工资是多少呢&#xff1f;这个其实也不好说&#xff0c;有时候曹操赚很多的钱&#xff0c;有时候也亏血本&#xff0c;甚至连脑袋都差点掉了。创业不容易啊&#xff0c;曹老板也是如…...

使用Element Plus

1. 官网安装 安装 | Element Plus (gitee.io) 安装&#xff1a; npm install element-plus --save 在main.ts中全局注册ElementPlus并使用 //加入element-plus import ElementPlus from element-plus; //加入element-plus样式 import element-plus/dist/index.css; import…...

单例(Singleton)设计模式总结

1. 设计模式概述&#xff1a; 设计模式是在大量的实践中总结和理论化之后优选的代码结构、编程风格、以及解决问题的思考方式。设计模式免去我们自己再思考和摸索。 就像是经典的棋谱&#xff0c;不同的棋局&#xff0c;我们用不同的棋谱。"套路"经典的设计模式一共有…...

LeetCode每日一题之专题一:双指针 ——快乐数

快乐数OJ链接&#xff1a;202. 快乐数 - 力扣&#xff08;LeetCode&#xff09; 题目&#xff1a; 题目分析: 为了房便叙述&#xff0c;将「对于⼀个正整数&#xff0c;每⼀次将该数替换为它每个位置上的数字的平方和」这⼀个 操作记为 x 操作&#xff1b; 题目告诉我们&#…...

Docker Desktop 不支持 host 网络模式

先把这个结论的放在前面&#xff0c;直接访问链接就能看到官方文档中已经明确说了不支持。 参考链接&#xff1a;docker desktop for windows 不支持 host 网络模式 以前对于 docker 的网络模式&#xff0c;一直只是了解&#xff0c;没有亲自尝试过。结果今天在尝试 docker 的 …...

Linux网络编程二(TCP图解三次握手及四次挥手、TCP滑动窗口、MSS、TCP状态转换、多进程/多线程服务器实现)

文章目录 1、TCP三次握手(1) 第一次握手(2) 第二次握手(3) 第三次握手 2、TCP四次挥手(1) 一次挥手(2) 二次挥手(3) 三次挥手(4) 四次挥手 3、TCP滑动窗口4、TCP状态时序图5、多进程并发服务器6、多线程并发服务器 1、TCP三次握手 TCP三次握手(TCP three-way handshake)是TCP协…...

【云原生篇】K8S之Job 和 CronJob

在 Kubernetes (K8s) 中&#xff0c;Job 和 CronJob 是两种管理批处理任务的资源对象&#xff0c;它们用于控制短暂的一次性任务&#xff08;Job&#xff09;或定时执行的周期性任务&#xff08;CronJob&#xff09;。 Job 概念 Job 负责运行一个或多个 Pod&#xff0c;并确…...

PHP8.3-ZTS版本安装流程以及添加扩展

下载php-8.3.x.tar.gz至服务器并解压 [rootapisix-test php-8.3.4]# wget https://www.php.net/distributions/php-8.3.4.tar.gz进入目录执行编译命令&#xff0c;必须要带 --enable-zts 才能激活zts功能 [rootapisix-test php-8.3.4]# ./configure --prefix/usr/local/p…...

RabbitMQ系统监控、问题排查和性能优化实践

一、系统监控&#xff1a;RabbitMQ的各项性能指标及监控 Message Rates&#xff1a;消息率包含了publish&#xff0c;deliver/get&#xff0c;ack等方面的数据&#xff0c;反映了消息在系统中流转的情况。Queue Length&#xff1a;队列长度反映了系统当前的负载情况。如果队列…...

【华为OD机试】根据IP查找城市(贪心算法—JavaPythonC++JS实现)

本文收录于专栏:算法之翼 本专栏所有题目均包含优质解题思路,高质量解题代码(Java&Python&C++&JS分别实现),详细代码讲解,助你深入学习,深度掌握! 文章目录 一. 题目二.解题思路三.题解代码Python题解代码JAVA题解代码C/C++题解代码JS题解代码四.代码讲解(Ja…...

css:阴影效果box-shadow

属性 box-shadow 属性值由四个参数组成&#xff1a; 水平偏移量&#xff1a;表示阴影相对于元素的水平位置。垂直偏移量&#xff1a;表示阴影相对于元素的垂直位置。模糊度&#xff1a;表示阴影的模糊程度。颜色&#xff1a;表示阴影的颜色 示例 单个box-shadow 0px -2px 6p…...

Scala第十九章节(Actor的相关概述、Actor发送和接收消息以及WordCount案例)

Scala第十九章节 章节目标 了解Actor的相关概述掌握Actor发送和接收消息掌握WordCount案例 1. Actor介绍 Scala中的Actor并发编程模型可以用来开发比Java线程效率更高的并发程序。我们学习Scala Actor的目的主要是为后续学习Akka做准备。 1.1 Java并发编程的问题 在Java并…...

蓝桥杯杯赛之深度优先搜索优化《1.分成互质组》 《 2.小猫爬山》【dfs】【深度搜索剪枝优化】【搜索顺序】

文章目录 思想例题1. 分成互质组题目链接题目描述【解法一】【解法二】 2. 小猫爬山题目链接题目描述输入样例&#xff1a;输出样例&#xff1a;【思路】【WA代码】【AC代码】 思想 本质为两种搜索顺序&#xff1a; 枚举当前元素可以放入哪一组枚举每一组可以放入哪些元素 操…...

软件设计原则:依赖倒置

定义 依赖倒置原则&#xff08;Dependency Inversion Principle, DIP&#xff09;是面向对象设计原则之一&#xff0c;其核心是高层模块&#xff08;如业务逻辑&#xff09;不应当依赖于低层模块&#xff08;如具体的数据访问或设备控制实现&#xff09;&#xff0c;而是双方都…...

03-自媒体文章发布

自媒体文章发布 1)自媒体前后端搭建 1.1)后台搭建 ①&#xff1a;资料中找到heima-leadnews-wemedia.zip解压 拷贝到heima-leadnews-service工程下&#xff0c;并指定子模块 执行leadnews-wemedia.sql脚本 添加对应的nacos配置 spring:datasource:driver-class-name: com…...

Oracle中实现一次插入多条数据

一、需求描述 在我们实际的业务场景中&#xff0c;由于单条插入的效率很低&#xff08;每次都需要数据库资源连接关闭的开销&#xff09;&#xff0c;故需要实现一次性插入多条数据&#xff0c;用以提升数据插入的效率&#xff1b; 如下图是常见的单条插入数据&#xff1a; 二…...

【C++入门】关键字、命名空间以及输入输出

&#x1f49e;&#x1f49e; 前言 hello hello~ &#xff0c;这里是大耳朵土土垚~&#x1f496;&#x1f496; &#xff0c;欢迎大家点赞&#x1f973;&#x1f973;关注&#x1f4a5;&#x1f4a5;收藏&#x1f339;&#x1f339;&#x1f339; &#x1f4a5;个人主页&#x…...

初识MySQL(中篇)

使用语言 MySQL 使用工具 Navicat Premium 16 代码能力快速提升小方法&#xff0c;看完代码自己敲一遍&#xff0c;十分有用 目录 1.SQL语言 1.1 SQL语言组成部分 2.MySQL数据类型 2.1 数值类型 2.2 字符串类型 2.3 日期类型 3.创建数据表 3.1 创建数据表方法1 …...

前端订阅后端推送WebSocket定时任务

0.需求 后端定时向前端看板推送数据&#xff0c;每10秒或者30秒推送一次。 1.前言知识 HTTP协议是一个应用层协议&#xff0c;它的特点是无状态、无连接和单向的。在HTTP协议中&#xff0c;客户端发起请求&#xff0c;服务器则对请求进行响应。这种请求-响应的模式意味着服务器…...

Linux链表操作全解析

Linux C语言链表深度解析与实战技巧 一、链表基础概念与内核链表优势1.1 为什么使用链表&#xff1f;1.2 Linux 内核链表与用户态链表的区别 二、内核链表结构与宏解析常用宏/函数 三、内核链表的优点四、用户态链表示例五、双向循环链表在内核中的实现优势5.1 插入效率5.2 安全…...

【学习笔记】深入理解Java虚拟机学习笔记——第4章 虚拟机性能监控,故障处理工具

第2章 虚拟机性能监控&#xff0c;故障处理工具 4.1 概述 略 4.2 基础故障处理工具 4.2.1 jps:虚拟机进程状况工具 命令&#xff1a;jps [options] [hostid] 功能&#xff1a;本地虚拟机进程显示进程ID&#xff08;与ps相同&#xff09;&#xff0c;可同时显示主类&#x…...

Device Mapper 机制

Device Mapper 机制详解 Device Mapper&#xff08;简称 DM&#xff09;是 Linux 内核中的一套通用块设备映射框架&#xff0c;为 LVM、加密磁盘、RAID 等提供底层支持。本文将详细介绍 Device Mapper 的原理、实现、内核配置、常用工具、操作测试流程&#xff0c;并配以详细的…...

Unity UGUI Button事件流程

场景结构 测试代码 public class TestBtn : MonoBehaviour {void Start(){var btn GetComponent<Button>();btn.onClick.AddListener(OnClick);}private void OnClick(){Debug.Log("666");}}当添加事件时 // 实例化一个ButtonClickedEvent的事件 [Formerl…...

【从零开始学习JVM | 第四篇】类加载器和双亲委派机制(高频面试题)

前言&#xff1a; 双亲委派机制对于面试这块来说非常重要&#xff0c;在实际开发中也是经常遇见需要打破双亲委派的需求&#xff0c;今天我们一起来探索一下什么是双亲委派机制&#xff0c;在此之前我们先介绍一下类的加载器。 目录 ​编辑 前言&#xff1a; 类加载器 1. …...

在 Spring Boot 中使用 JSP

jsp&#xff1f; 好多年没用了。重新整一下 还费了点时间&#xff0c;记录一下。 项目结构&#xff1a; pom: <?xml version"1.0" encoding"UTF-8"?> <project xmlns"http://maven.apache.org/POM/4.0.0" xmlns:xsi"http://ww…...

二维FDTD算法仿真

二维FDTD算法仿真&#xff0c;并带完全匹配层&#xff0c;输入波形为高斯波、平面波 FDTD_二维/FDTD.zip , 6075 FDTD_二维/FDTD_31.m , 1029 FDTD_二维/FDTD_32.m , 2806 FDTD_二维/FDTD_33.m , 3782 FDTD_二维/FDTD_34.m , 4182 FDTD_二维/FDTD_35.m , 4793...

[特殊字符] 手撸 Redis 互斥锁那些坑

&#x1f4d6; 手撸 Redis 互斥锁那些坑 最近搞业务遇到高并发下同一个 key 的互斥操作&#xff0c;想实现分布式环境下的互斥锁。于是私下顺手手撸了个基于 Redis 的简单互斥锁&#xff0c;也顺便跟 Redisson 的 RLock 机制对比了下&#xff0c;记录一波&#xff0c;别踩我踩过…...

【笔记】AI Agent 项目 SUNA 部署 之 Docker 构建记录

#工作记录 构建过程记录 Microsoft Windows [Version 10.0.27871.1000] (c) Microsoft Corporation. All rights reserved.(suna-py3.12) F:\PythonProjects\suna>python setup.py --admin███████╗██╗ ██╗███╗ ██╗ █████╗ ██╔════╝…...

Pandas 可视化集成:数据科学家的高效绘图指南

为什么选择 Pandas 进行数据可视化&#xff1f; 在数据科学和分析领域&#xff0c;可视化是理解数据、发现模式和传达见解的关键步骤。Python 生态系统提供了多种可视化工具&#xff0c;如 Matplotlib、Seaborn、Plotly 等&#xff0c;但 Pandas 内置的可视化功能因其与数据结…...