蓝桥杯每日一题:斐波那契(矩阵乘法)

在斐波那契数列中,Fib0=0,Fib1=1,Fibn=Fibn−1+Fibn−2(n>1)

给定整数 n,求 Fibnmod10000。

输入格式

输入包含不超过 100100 组测试用例。

每个测试用例占一行,包含一个整数 

当输入用例 n=−1时,表示输入终止,且该用例无需处理。

输出格式

每个测试用例输出一个整数表示结果。

每个结果占一行。

数据范围

0≤n≤2×10^9

输入样例:
0
9
999999999
1000000000
-1
输出样例:
0

解题思路:

矩阵求fib:

定义a[2][2] = {0,1,0,0} f[2][2]={0,1,1,1}

an=a0*f^n

 最后a[0][0]就是答案

/*

矩阵求fib,
*/
#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
const int MOD = 10000;

int mul(int a[][2],int b[][2])
{
    int c[2][2] = {0};
    for(int i=0;i<2;i++)
       for(int j=0;j<2;j++)
         for(int k=0;k<2;k++)
            c[i][j] = (c[i][j] + a[i][k] * b[j][k]) % MOD;
    memcpy(a,c,sizeof c);        
}

int fib(int n)
{
    int a[2][2] = {0,1,0,0};
    int f[2][2] = {0,1,1,1};
    
    while (n)
    {
        if(n&1) mul(a,f);
        mul(f,f);
        n >>= 1;
    }
    return a[0][0];
}

int main()
{
    int n;
    while(cin>>n,n!=-1)
     cout<<fib(n)<<endl;
    return 0; 
}

 

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

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

相关文章

Python环境搭建—安装PyCharm开发工具

&#x1f947;作者简介&#xff1a;CSDN内容合伙人、新星计划第三季Python赛道Top1 &#x1f525;本文已收录于Python系列专栏&#xff1a; 零基础学Python &#x1f4ac;订阅专栏后可私信博主进入Python学习交流群&#xff0c;进群可领取Python视频教程以及Python相关电子书合…

JS详解-设计模式

工厂模式&#xff1a; 单例模式&#xff1a; // 1、定义一个类class SingleTon{// 2、添加私有静态属性static #instance// 3、添加静态方法static getInstance(){// 4、判断实例是否存在if(!this.#instance){// 5、实例不存在&#xff0c;创建实例this.#instance new Single…

rust项目组织结构和集成测试举例

概述 在学习rust的过程中&#xff0c;当项目结构略微复杂的时候&#xff0c;写集成测试的时候发现总是不能引用项目中的代码&#xff0c;导致编写测试用例失败。查阅了教程&#xff0c;一般举例都很简单。查阅了谷歌和百度以及ai&#xff0c;也没有找到满意的答案。这里记录一…

Spring Boot 接入 Redis

Spring Boot 接入 Redis 简介 Redis 是一种访问速度非常快的内存数据结构存储&#xff0c;用作数据库、缓存、消息代理和流引擎。提供 strings、hashes、lists、sets 等数据结构。可以解决会话缓存、消息队列、分布式锁、定期将数据集存储到硬盘等功能。 通过 Redis 设计实现…

win11 安全中心打开黑屏\白屏\打不开有效解决

文章目录 问题和解决思路解决方法 问题和解决思路 问题&#xff1a;在重装和或者初次安装系统后&#xff0c;win11安全中心无法成功启动解决思路&#xff1a;直接重装安全中心&#xff0c;解决问题&#xff08;作者尝试了修复和重置的功能–无效&#xff09;视频教程参考WIN11…

攻防世界:mfw[WriteUP]

根据题目提示考虑是git库泄露 这里在地址栏后加.git也可以验证是git库泄露 使用GitHack工具对git库进行恢复重建 在templates目录下存在flag.php文件&#xff0c;但里面并没有flag 有内容的只有主目录下的index.php index.php源码&#xff1a; <?phpif (isset($_GET[page…

Photoshop 2024 中文---专业图像处理软件的又一次飞跃

Photoshop 2024是一款功能强大的图像处理软件&#xff0c;广泛应用于创意设计和图像处理领域。它提供了丰富的绘画和编辑工具&#xff0c;包括画笔、铅笔、颜色替换、混合器画笔等&#xff0c;使用户能够轻松进行图片编辑、合成、校色、抠图等操作&#xff0c;实现各种视觉效果…

Nature正刊重磅!热带雨林正接近临界温度阈值:气候变化可能会使热带森林太热而无法进行光合作用

2023年8月23日&#xff0c;美国北亚利桑那大学生态信息学Doughty, Christopher E. 副教授及其研究组人员在国际知名学术期刊《Nature》发表了一项题为“Tropical forests are approaching critical temperature thresholds”的研究。提出了热带雨林正接近临界温度阈值的新见解。…

vivado 有关 SVF 链的操作

按正确顺序创建反映所有器件及其配置存储器的 SVF 链之后 &#xff0c; 即可开始向 SVF 链中的器件添加编程操作。 例如&#xff0c; 您可右键单击链中的赛灵思 a200t 器件 &#xff0c; 然后选择“添加器件编程操作 (Add Program Device Operation) ”对话 框&#xff0c; …

数据导出实践:Spring Boot实现高效的千万数据导出

当数据量达到千万级别时&#xff0c;传统的导出方式往往效率低下&#xff0c;甚至可能导致系统崩溃。 数据导出的挑战 在实现千万数据导出功能时&#xff0c;常常会面临以下挑战&#xff1a; 内存占用过高&#xff1a;传统的导出方式往往需要将所有数据加载到内存中&#xff0…

【airtest】自动化入门教程(四)Poco元素定位

目录 一、基础操作 1、通过属性名等方式 2、通过属性组合 3、子节点方式 4、子节点加属性组合方式 5、孙节点offspring 6、兄弟节点sibling 7、父节点parent 8、正则表达式 9、直到某个元素出现 10、直到某个元素消失 二、通过局部坐标定位 1、使用局部坐标系的cli…

这下 package.json 里面的字段就清楚了

npm package.json 文件的详细说明。 Version:9.8.1 本文档包含了关于 package.json 文件中所需内容的所有信息。它必须是有效的 JSON 格式&#xff0c;而不仅仅是 JavaScript 对象字面量。 1. name 如果您计划发布您的包&#xff0c;那么 package.json 文件中最重要的字段是 n…

美食分享|基于Springboot和vue的地方美食分享网站系统设计与实现(源码+数据库+文档)

地方美食分享网站系统 目录 基于Springboot和vue的地方美食分享网站系统设计与实现 一、前言 二、系统设计 三、系统功能设计 1、前台&#xff1a; 2、后台 四、数据库设计 五、核心代码 六、论文参考 七、最新计算机毕设选题推荐 八、源码获取&#xff1a; 博主介…

HTTP协议报文的结构

如图在要将数据传输给服务器时&#xff0c;通常会将用到上图中的GEA等请求。 GET请求&#xff0c;通常会将要传给服务器的数据&#xff0c;加到url的query string中body中 还有POST请求&#xff0c;通常把要传给服务器的数据加入到body中。 上述都是习惯用法&#xff08;都是…

蓝桥集训之斐波那契数列

蓝桥集训之斐波那契数列 核心思想&#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…

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*…