当前位置: 首页 > 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;服务器则对请求进行响应。这种请求-响应的模式意味着服务器…...

提高机器人系统稳定性:引入阻尼作为共振后的相位超前

在机器人关节中&#xff0c;引入阻尼作为共振后的相位超前&#xff0c;确实是一种提高系统稳定性的有效策略。机器人关节的振动和共振是影响其性能稳定性的关键因素&#xff0c;特别是在进行高速、高精度操作时。阻尼的引入能够显著减少这些不利因素&#xff0c;提升机器人的整…...

深度学习理论基础(三)封装数据集及手写数字识别

目录 前期准备一、制作数据集1. excel表格数据2. 代码 二、手写数字识别1. 下载数据集2. 搭建模型3. 训练网络4. 测试网络5. 保存训练模型6. 导入已经训练好的模型文件7. 完整代码 前期准备 必须使用 3 个 PyTorch 内置的实用工具&#xff08;utils&#xff09;&#xff1a; ⚫…...

vue3+eachrts饼图轮流切换显示高亮数据

<template><div class"charts-box"><div class"charts-instance" ref"chartRef"></div>// 自定义legend 样式<div class"charts-note"><span v-for"(items, index) in data.dataList" cla…...

UTONMOS:AI+Web3+元宇宙数字化“三位一体”将触发经济新爆点

人工智能、元宇宙、Web3&#xff0c;被称为数字化的“三位一体”&#xff0c;如何看待这三大技术所扮演的角色&#xff1f; 3月24日&#xff0c;2024全球开发者先锋大会“数字化的三位一体——人工智能、元宇宙、Web3.0”论坛在上海漕河泾开发区举行&#xff0c;首次提出&…...

开始焦虑了

大家好&#xff0c;我是洋子&#xff0c;25届的暑期实习自从3月份开始招聘有一段时间了&#xff0c;最近接到了几个25届同学的咨询&#xff0c;其中一个学妹印象比较深刻&#xff0c;她的情况如下 个人情况 学历是双非本&#xff0c;计算机专业&#xff0c;学习方向是Java&…...

数据结构和算法:十大排序

排序算法 排序算法用于对一组数据按照特定顺序进行排列。排序算法有着广泛的应用&#xff0c;因为有序数据通常能够被更高效地查找、分析和处理。 排序算法中的数据类型可以是整数、浮点数、字符或字符串等。排序的判断规则可根据需求设定&#xff0c;如数字大小、字符 ASCII…...

LLaMA-Factory微调(sft)ChatGLM3-6B保姆教程

LLaMA-Factory微调&#xff08;sft&#xff09;ChatGLM3-6B保姆教程 准备 1、下载 下载LLaMA-Factory下载ChatGLM3-6B下载ChatGLM3windows下载CUDA ToolKit 12.1 &#xff08;本人是在windows进行训练的&#xff0c;显卡GTX 1660 Ti&#xff09; CUDA安装完毕后&#xff0c…...

Web安全-浏览器安全策略及跨站脚本攻击与请求伪造漏洞原理

Web安全-浏览器安全策略及跨站脚本攻击与请求伪造漏洞原理 Web服务组件分层概念 静态层 &#xff1a;web前端框架&#xff1a;Bootstrap&#xff0c;jQuery,HTML5框架等&#xff0c;主要存在跨站脚本攻击脚本层&#xff1a;web应用&#xff0c;web开发框架&#xff0c;web服务…...

蓝桥杯B组C++省赛——飞机降落(DFS)

题目连接&#xff1a;https://www.lanqiao.cn/problems/3511/learning/ 思路&#xff1a;由于数据范围很小&#xff0c;所有选择用DFS枚举所有飞机的所有的降落顺序&#xff0c;看哪个顺序可以让所有飞机顺利降落&#xff0c;有的话就算成功方案&#xff0c;输出了“YES”。 …...

Java 中的 Map集合

文章目录 添加和修改元素获取元素检查元素删除元素获取所有键 / 值 / 键值对大小 在 Java 中&#xff0c;Map 接口是 Java 集合框架的一部分&#xff0c;它存储键值对&#xff08;key-value pairs&#xff09;。Map 接口有许多常用的方法&#xff0c;用于添加、删除、获取元素&…...

wordpress 小清新主题/查淘宝关键词排名软件

这个视频&#xff0c;我会把入驻抖音小店的所有步骤、细节及注意事项&#xff0c;全部整理下来&#xff0c;避免粉丝朋友们采坑&#xff01; 不知道前两天的文章你们看了没&#xff0c;但是我可以很负责的保证&#xff0c;如果你能把我这个抖音小店玩法系列的教程认真看完&…...

网站建设云主机云服务器/网站外链的优化方法

我国基因编辑技术的研发领先全球&#xff0c;但由于尚未出台基因编辑产品管理政策&#xff0c;相关产业面临技术研究领先、管理滞后、应用空白的局面。与会专家学者、企业代表纷纷结合国外基因编辑监管措施建言献策&#xff0c;呼吁基因编辑政策早日出台。 “目前&#xff0c;…...

开发平台英文/成都seo培训班

我试着统计双元组出现的频率&#xff0c;并列出最常见的5个。我可以打印输出&#xff0c;但当我尝试使用saveAsTextFile以.out文件格式保存结果时&#xff0c;会出现“属性错误”。在from __future__ import print_functionimport sysfrom operator import addfrom pyspark imp…...

内容电商的网站如何做/桔子seo查询

mysql查询今天,昨天,近7天,近30天,本月,上一月数据最近项目中用到了查询当月数据记录的功能&#xff0c;最初的想法是在逻辑业务里构造好时间段进行查询&#xff0c;当写sql语句时感觉挺麻烦。所以就到网上搜索了一下&#xff0c;看看是不是能有简单的方法。果然&#xff0c;网…...

网站移动端是什么问题/网络游戏推广

在开始读书会开始前,还是要重申读书会的意义,从目前的知识体系来看,当今的人们接触的大多是碎片化的信息, 也就是需要哪个看那个,出了问题解决那个问题,看似在当今的社会中,大部分人都是这样解决问题的,但碎片化的知识会带来的问题是,看问题不全面, 解决问题可能只会往一个方向…...

安徽有几家做网站/引流推广平台有哪些

函数或者信号在各个领域都是被人们广泛研究的课题。而傅里叶级数从时域和频域两个角度对信号进行研究和计算&#xff0c;无论在理论上或者实践中都有重要的意义和价值&#xff0c;很多人都在学习和研究这个理论。图1所示为一个下锯齿形信号&#xff0c;右面的时域图表示随时间变…...