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

斐波那契1(矩阵快速幂加速递推,斐波那契前n项平方和)

链接:登录—专业IT笔试面试备考平台_牛客网
来源:牛客网
 

Keven 特别喜欢斐波那契数列,已知 fib1=1fib_1=1fib1​=1,fib2=1fib_2=1fib2​=1,对于 n>=3n>=3n>=3,fibn=fibn−2+fibn−1fib_{n}=fib_{n-2}+fib_{n-1}fibn​=fibn−2​+fibn−1​,并且他想知道斐波那契前 nnn 项平方和是多少?

为了防止答案过大,请将最后的答案模 1e9+71e9+71e9+7


代码:

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=1e9+7;
struct jz
{ll m[2][2];
};
jz operator * (const jz &a,const jz &b)//*,矩阵乘法的重载运算符
{jz c;memset(c.m,0,sizeof c.m);for(ll i=0;i<2;i++){for(ll j=0;j<2;j++){for(ll k=0;k<2;k++){c.m[i][j]=(c.m[i][j]+a.m[i][k]*b.m[k][j])%mod;}}}return c;
}
jz pow(jz a,ll b)
{jz res;memset(res.m,0,sizeof res.m);for(ll i=0;i<2;i++)res.m[i][i]=1;while(b){if(b&1)res=res*a;b>>=1;a=a*a;}return res;
}
ll mul(ll a,ll b,ll mod)//乘法模
{a=a%mod;b=b%mod;ll res=0;while(b){if(b&1)res=(res+a)%mod;b>>=1;a=(a+a)%mod;}return res;
}
void solve()
{ll n;cin>>n;jz ans;ans.m[0][0]=1;//赋值,先通过递推公式,确定abcd的值,d为0,其他为1ans.m[0][1]=1;ans.m[1][0]=1;ans.m[1][1]=0;jz md=pow(ans,n);cout<<mul(md.m[0][0],md.m[0][1],mod);
}
int main()
{ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);ll t=1;while(t--)solve();return 0;
}

相关文章:

斐波那契1(矩阵快速幂加速递推,斐波那契前n项平方和)

链接&#xff1a;登录—专业IT笔试面试备考平台_牛客网 来源&#xff1a;牛客网 Keven 特别喜欢斐波那契数列&#xff0c;已知 fib11fib_11fib1​1&#xff0c;fib21fib_21fib2​1&#xff0c;对于 n>3n>3n>3&#xff0c;fibnfibn−2fibn−1fib_{n}fib_{n-2}fib_{n…...

minikube mac 启动

系统信息如下 最开始使用的minikube是1.22.0版本&#xff0c;按照如下命令启动&#xff1a; minikube start --memory7851 --cpus4 --image-mirror-countrycn遇到了下面一些问题&#xff1a; 1、拉取coredns:v1.8.0镜像失败 Error response from daemon: manifest for regis…...

从零开始学习 Java:简单易懂的入门指南之查找算法及排序算法(二十)

查找算法及排序算法 常见的七种查找算法&#xff1a;1. 基本查找2. 二分查找3. 插值查找4. 斐波那契查找5. 分块查找6. 哈希查找7. 树表查找 四种排序算法&#xff1a;1. 冒泡排序1.1 算法步骤1.2 动图演示1.3 代码示例 2. 选择排序2.1 算法步骤2.2 动图演示 3. 插入排序3.1 算…...

非煤矿山风险监测预警算法 yolov8

非煤矿山风险监测预警算法通过yolov8网络模型深度学习算法框架&#xff0c;非煤矿山风险监测预警算法在煤矿关键地点安装摄像机等设备利用智能化视频识别技术&#xff0c;能够实时分析人员出入井口的情况&#xff0c;人数变化并检测作业状态。YOLO的结构非常简单&#xff0c;就…...

Ansible学习笔记(一)

1.什么是Ansible 官方网站&#xff1a;https://docs.ansible.com/ansible/latest/installation_guide/intro_installation.html Ansible是一个配置管理和配置工具&#xff0c;类似于Chef&#xff0c;Puppet或Salt。这是一款很简单也很容易入门的部署工具&#xff0c;它使用SS…...

2024毕业设计选题指南【附选题大全】

title: 毕业设计选题指南 - 如何选择合适的毕业设计题目 date: 2023-08-29 categories: 毕业设计 tags: 选题指南, 毕业设计, 毕业论文, 毕业项目 - 如何选择合适的毕业设计题目 当我们站在大学生活的十字路口&#xff0c;毕业设计便成了我们面临的一项重要使命。这不仅是对我们…...

Error: PostCSS plugin autoprefixer requires PostCSS 8 问题解决办法

报错&#xff1a;Error: PostCSS plugin autoprefixer requires PostCSS 8 原因&#xff1a;autoprefixer版本过高 解决方案&#xff1a; 降低autoprefixer版本 执行&#xff1a;npm i postcss-loader autoprefixer8.0.0...

pymongo通过oplog获取数据(mongodb)

使用 MongoDB 的 oplog&#xff08;操作日志&#xff09;进行数据同步是高级的用法&#xff0c;主要用于复制和故障恢复。需要确保源 MongoDB 实例是副本集的一部分&#xff0c;因为只有副本集才会维护 oplog。 以下是简化的步骤&#xff0c;描述如何使用 oplog 进行数据同步&…...

MySQL数据备份与恢复

备份的主要目的&#xff1a; 备份的主要目的是&#xff1a;灾难恢复&#xff0c;备份还可以测试应用、回滚数据修改、查询历史数据、审计等。 日志&#xff1a; MySQL 的日志默认保存位置为&#xff1a; /usr/local/mysql/data##配置文件 vim /etc/my.cnf [mysqld] ##错误日志…...

基于ssm+vue汽车售票网站源码和论文

基于ssmvue汽车售票网站源码和论文088 开发工具&#xff1a;idea 数据库mysql5.7 数据库链接工具&#xff1a;navcat,小海豚等 技术&#xff1a;ssm 摘 要 互联网发展至今&#xff0c;无论是其理论还是技术都已经成熟&#xff0c;而且它广泛参与在社会中的方方面面。它让…...

【List】List集合有序测试案例:ArrayList,LinkedList,Vector(123)

List是有序、可重复的容器。 有序&#xff1a; List中每个元素都有索引标记。可以根据元素的索引标记(在List中的位置)访问 元素&#xff0c;从而精确控制这些元素。 可重复&#xff1a; List允许加入重复的元素。更确切地讲&#xff0c;List通常允许满足 e1.equals(e2) 的元素…...

【javaweb】学习日记Day6 - Mysql 数据库 DDL DML

之前学习过的SQL语句笔记总结戳这里→【数据库原理与应用 - 第六章】T-SQL 在SQL Server的使用_Roye_ack的博客-CSDN博客 目录 一、概述 1、如何安装及配置路径Mysql&#xff1f; 2、SQL分类 二、DDL 数据定义 1、数据库操作 2、IDEA内置数据库使用 &#xff08;1&…...

使用 PyTorch C ++前端

使用 PyTorch C 前端 PyTorch C 前端是 PyTorch 机器学习框架的纯 C 接口。 虽然 PyTorch 的主要接口自然是 Python&#xff0c;但此 Python API 建立于大量的 C 代码库之上&#xff0c;提供基本的数据结构和功能&#xff0c;例如张量和自动微分。 C 前端公开了纯 C 11 API&a…...

6、NoSQL的四大分类

6、NoSQL的四大分类 kv键值对 不同公司不同的实现 新浪&#xff1a;Redis美团&#xff1a;RedisTair阿里、百度&#xff1a;Redismemcache 文档型数据库&#xff08;bson格式和json一样&#xff09; MongoDB MongoDB是一个基于分布式文件存储的数据库&#xff0c;一般用于存储…...

(动态规划) 剑指 Offer 60. n个骰子的点数 ——【Leetcode每日一题】

❓ 剑指 Offer 60. n个骰子的点数 难度&#xff1a;中等 把 n 个骰子扔在地上&#xff0c;所有骰子朝上一面的点数之和为 s 。输入 n&#xff0c;打印出s的所有可能的值出现的概率。 你需要用一个浮点数数组返回答案&#xff0c;其中第 i 个元素代表这 n 个骰子所能掷出的点…...

ArrayList与顺序表

文章目录 一. 顺序表是什么二. ArrayList是什么三. ArrayList的构造方法四. ArrayList的常见方法4.1 add()4.2 size()4.3 remove()4.4 get()4.5 set()4.6 contains()4.7 lastIndexOf()和 indexOf(&#xff09;4.8 subList()4.9 clear() 以上就是ArrayList的常见方法&#xff01…...

【【萌新的STM32-22中断概念的简单补充】】

萌新的STM32学习22-中断概念的简单补充 我们需要注意的是这句话 从上面可以看出&#xff0c;STM32F1 供给 IO 口使用的中断线只有 16 个&#xff0c;但是 STM32F1 的 IO 口却远远不止 16 个&#xff0c;所以 STM32 把 GPIO 管脚 GPIOx.0~GPIOx.15(xA,B,C,D,E,F,G)分别对应中断…...

Java 中数据结构HashMap的用法

Java HashMap HashMap 是一个散列表&#xff0c;它存储的内容是键值对(key-value)映射。 HashMap 实现了 Map 接口&#xff0c;根据键的 HashCode 值存储数据&#xff0c;具有很快的访问速度&#xff0c;最多允许一条记录的键为 null&#xff0c;不支持线程同步。 HashMap 是…...

Request对象和response对象

一、概念 request对象和response对象是通过Servlet容器&#xff08;如Tomcat&#xff09;自动创建并传递给Servlet的。 Servlet容器负责接收客户端的请求&#xff0c;并将请求信息封装到request对象中&#xff0c;然后将request对象传 递给相应的Servlet进行处理。类似地&…...

设计模式之桥接模式

文章目录 一、介绍二、案例1. 组件抽象化2. 桥梁抽象化 一、介绍 桥接模式&#xff0c;属于结构型设计模式。通过提供抽象与实现之间的桥接结构&#xff0c;把抽象化与实现化解耦&#xff0c;使得二者可以独立变化。 《Head First 设计模式》&#xff1a; 将抽象和实现放在两…...

大型活动交通拥堵治理的视觉算法应用

大型活动下智慧交通的视觉分析应用 一、背景与挑战 大型活动&#xff08;如演唱会、马拉松赛事、高考中考等&#xff09;期间&#xff0c;城市交通面临瞬时人流车流激增、传统摄像头模糊、交通拥堵识别滞后等问题。以演唱会为例&#xff0c;暖城商圈曾因观众集中离场导致周边…...

【快手拥抱开源】通过快手团队开源的 KwaiCoder-AutoThink-preview 解锁大语言模型的潜力

引言&#xff1a; 在人工智能快速发展的浪潮中&#xff0c;快手Kwaipilot团队推出的 KwaiCoder-AutoThink-preview 具有里程碑意义——这是首个公开的AutoThink大语言模型&#xff08;LLM&#xff09;。该模型代表着该领域的重大突破&#xff0c;通过独特方式融合思考与非思考…...

鱼香ros docker配置镜像报错:https://registry-1.docker.io/v2/

使用鱼香ros一件安装docker时的https://registry-1.docker.io/v2/问题 一键安装指令 wget http://fishros.com/install -O fishros && . fishros出现问题&#xff1a;docker pull 失败 网络不同&#xff0c;需要使用镜像源 按照如下步骤操作 sudo vi /etc/docker/dae…...

基于Java Swing的电子通讯录设计与实现:附系统托盘功能代码详解

JAVASQL电子通讯录带系统托盘 一、系统概述 本电子通讯录系统采用Java Swing开发桌面应用&#xff0c;结合SQLite数据库实现联系人管理功能&#xff0c;并集成系统托盘功能提升用户体验。系统支持联系人的增删改查、分组管理、搜索过滤等功能&#xff0c;同时可以最小化到系统…...

Go 并发编程基础:通道(Channel)的使用

在 Go 中&#xff0c;Channel 是 Goroutine 之间通信的核心机制。它提供了一个线程安全的通信方式&#xff0c;用于在多个 Goroutine 之间传递数据&#xff0c;从而实现高效的并发编程。 本章将介绍 Channel 的基本概念、用法、缓冲、关闭机制以及 select 的使用。 一、Channel…...

CSS | transition 和 transform的用处和区别

省流总结&#xff1a; transform用于变换/变形&#xff0c;transition是动画控制器 transform 用来对元素进行变形&#xff0c;常见的操作如下&#xff0c;它是立即生效的样式变形属性。 旋转 rotate(角度deg)、平移 translateX(像素px)、缩放 scale(倍数)、倾斜 skewX(角度…...

springboot 日志类切面,接口成功记录日志,失败不记录

springboot 日志类切面&#xff0c;接口成功记录日志&#xff0c;失败不记录 自定义一个注解方法 import java.lang.annotation.ElementType; import java.lang.annotation.Retention; import java.lang.annotation.RetentionPolicy; import java.lang.annotation.Target;/***…...

Spring Security 认证流程——补充

一、认证流程概述 Spring Security 的认证流程基于 过滤器链&#xff08;Filter Chain&#xff09;&#xff0c;核心组件包括 UsernamePasswordAuthenticationFilter、AuthenticationManager、UserDetailsService 等。整个流程可分为以下步骤&#xff1a; 用户提交登录请求拦…...

算法打卡第18天

从中序与后序遍历序列构造二叉树 (力扣106题) 给定两个整数数组 inorder 和 postorder &#xff0c;其中 inorder 是二叉树的中序遍历&#xff0c; postorder 是同一棵树的后序遍历&#xff0c;请你构造并返回这颗 二叉树 。 示例 1: 输入&#xff1a;inorder [9,3,15,20,7…...

字符串哈希+KMP

P10468 兔子与兔子 #include<bits/stdc.h> using namespace std; typedef unsigned long long ull; const int N 1000010; ull a[N], pw[N]; int n; ull gethash(int l, int r){return a[r] - a[l - 1] * pw[r - l 1]; } signed main(){ios::sync_with_stdio(false), …...