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

矩阵的c++实现(2)

上一次我们了解了矩阵的运算和如何使用矩阵解决斐波那契数列,这一次我们多看看例题,了解什么情况下用矩阵比较合适。

先看例题

1.洛谷P1939 【模板】矩阵加速(数列)

模板题应该很简单。

补:1<n<=10^9

10^9肯定超了,所以可以用矩阵做

我们可以观察到,每一项(x>3)都是由两个量组成,于是创建矩阵:

A=[a_{n-1},a_{n-3}]

同时:B=A\times base=[a_{n},?]

那么因为如果要再让A\times base\times base=[a_{n+1},??],A*base 之后还是应该是前一个为一项,后一项为它的两项前。所以?处应为a_{n-2}。??处应为什么自己想想,发在评论区里吧。

但是,a_{n-2}在A中并没有出现,这样我们就不可以用A*base表示B了,因为矩阵的乘法中,必须要上一个矩阵中有的元素,才能进入下一个矩阵中。

无论怎样,a_{n-2}都无法表示为n\times a_{n-1}+m\times a_{n-2}的形式,所以B不可以由A构成。

那这个时候就可以用一个巧妙的方法:我们在A和B中都增加a_{n-2}这一项,这样就会变成

[a_{n-1},a_{n-2},a_{n-3}]\times base=[a_{n},a_{n-1},a_{n-2}]

a_{n}可以表示为a_{n-1}+a_{n-3},这样就可以满足每一个条件都可以了。

那么我们利用矩阵乘法,在纸上演算七七四十八个小时,就可以得出,

base=\begin{bmatrix} 1,1,0\\ 0,0,1\\ 1,0,0\\ \end{bmatrix}

那么用和斐波那契数列一样的做法,快速幂即可

#include<bits/stdc++.h>
using namespace std;
#define mod 1000000007
struct Matrix{int n,m;long long a[100][100];Matrix(){memset(a,0,sizeof(a));}Matrix(int _n,int _m){n=_n;m=_m;memset(a,0,sizeof(a));}
};
Matrix ans(1,3);
Matrix base(3,3);
void init(){ans.a[0][0]=1;ans.a[0][1]=1;ans.a[0][2]=1;base.a[0][0]=1;base.a[0][1]=1;base.a[0][2]=0;base.a[1][0]=0;base.a[1][1]=0;base.a[1][2]=1;base.a[2][0]=1;base.a[2][1]=0;base.a[2][2]=0;
}
Matrix mul(Matrix a,Matrix b){Matrix res(a.n,b.m);for(int i=0;i<a.n;i++){for(int j=0;j<b.m;j++){for(int k=0;k<a.m;k++){res.a[i][j]+=a.a[i][k]*b.a[k][j]%mod;}res.a[i][j]%=mod;}}return res;
}
Matrix bpow(Matrix a,long long n){Matrix res(a.n,a.n);for(int i=0;i<a.n;i++)res.a[i][i]=1;while(n!=0){if(n&1){res=mul(res,a);}a=mul(a,a);n>>=1;}return res;
}
long long F(long long n){base=bpow(base,n-3);/*for(int i=0;i<3;i++){for(int j=0;j<3;j++){cout<<base.a[i][j];}cout<<endl;}*/ans=mul(ans,base);return ans.a[0][0]%mod;
}
int main(){long long t;cin>>t;while(t--){long long n;cin>>n;if(n<=3){cout<<1<<endl;continue;}init();cout<<F(n)<<endl;}return 0;
}

2.洛谷P1349 广义斐波那契数列

其实很简单,就是把斐波那契数列的模板套一下

先写一半

相关文章:

矩阵的c++实现(2)

上一次我们了解了矩阵的运算和如何使用矩阵解决斐波那契数列&#xff0c;这一次我们多看看例题&#xff0c;了解什么情况下用矩阵比较合适。 先看例题 1.洛谷P1939 【模板】矩阵加速&#xff08;数列&#xff09; 模板题应该很简单。 补&#xff1a;1<n<10^9 10^9肯定…...

RPC 框架之Thrift入门(一)

&#x1f4cb; 个人简介 &#x1f496; 作者简介&#xff1a;大家好&#xff0c;我是阿牛&#xff0c;全栈领域优质创作者。&#x1f61c;&#x1f4dd; 个人主页&#xff1a;馆主阿牛&#x1f525;&#x1f389; 支持我&#xff1a;点赞&#x1f44d;收藏⭐️留言&#x1f4d…...

【C++】运算符重载 ⑥ ( 一元运算符重载 | 后置运算符重载 | 前置运算符重载 与 后置运算符重载 的区别 | 后置运算符重载添加 int 占位参数 )

文章目录 一、后置运算符重载1、前置运算符重载 与 后置运算符重载 的区别2、后置运算符重载添加 int 占位参数 上 2 2 2 篇博客 【C】运算符重载 ④ ( 一元运算符重载 | 使用 全局函数 实现 前置 自增运算符重载 | 使用 全局函数 实现 前置 - - 自减运算符重载 )【C】运算符…...

538. 把二叉搜索树转换为累加树

题目描述 给出二叉 搜索 树的根节点&#xff0c;该树的节点值各不相同&#xff0c;请你将其转换为累加树&#xff08;Greater Sum Tree&#xff09;&#xff0c;使每个节点 node 的新值等于原树中大于或等于 node.val 的值之和。 提醒一下&#xff0c;二叉搜索树满足下列约束…...

java8日期时间工具类

【README】 1&#xff09;本文总结了java8中日期时间常用工具方法&#xff1b;包括&#xff1a; 日期时间对象格式化为字符串&#xff1b;日期时间字符串解析为日期时间对象&#xff1b;日期时间对象转换&#xff1b; 转换过程中&#xff0c;需要注意的是&#xff1a; Instan…...

算法-动态规划/trie树-单词拆分

算法-动态规划/trie树-单词拆分 1 题目概述 1.1 题目出处 https://leetcode.cn/problems/word-break/description/?envTypestudy-plan-v2&envIdtop-interview-150 1.2 题目描述 2 动态规划 2.1 解题思路 dp[i]表示[0, i)字符串可否构建那么dp[i]可构建的条件是&…...

React框架核心原理

一、整体架构 三大核心库与对应的组件 history -> react-router -> react-router-dom react-router 可视为react-router-dom 的核心&#xff0c;里面封装了<Router>&#xff0c;<Route>&#xff0c;<Switch>等核心组件,实现了从路由的改变到组件的更新…...

python-pytorch 利用pytorch对堆叠自编码器进行训练和验证

利用pytorch对堆叠自编码器进行训练和验证 一、数据生成二、定义自编码器模型三、训练函数四、训练堆叠自编码器五、将已训练的自编码器级联六、微调整个堆叠自编码器 一、数据生成 随机生成一些数据来模拟训练和验证数据集&#xff1a; import torch# 随机生成数据 n_sample…...

制作 3 档可调灯程序编写

PWM 0~255 可以将数据映射到0 75 150 225 尽可能均匀电压间隔...

源码分享-M3U8数据流ts的AES-128解密并合并---GoLang实现

之前使用C语言实现了一次&#xff0c;见M3U8数据流ts的AES-128解密并合并。 学习了Go语言后&#xff0c;又用Go重新实现了一遍。源码如下&#xff0c;无第三方库依赖。 package mainimport ("crypto/aes""crypto/cipher""encoding/binary"&quo…...

CSDN Q: “这段代码算是在STC89C52RC51单片机上完成PWM呼吸灯了吗?“

这是 CSDN上的一个问题 这段代码算是在STC89C52RC51单片机上完成PWM呼吸灯了吗&#xff0c;还是说得用上定时器和中断函数#include <regx52.h> 我个人认为: 效果上来说, 是的! 码以 以Time / 100-Time 调 Duty, 而 for i loop成 Period, 加上延时, 实现了 PWM周期, 虽然…...

Linux系统编程系列之线程池

Linux系统编程系列&#xff08;16篇管饱&#xff0c;吃货都投降了&#xff01;&#xff09; 1、Linux系统编程系列之进程基础 2、Linux系统编程系列之进程间通信(IPC)-信号 3、Linux系统编程系列之进程间通信(IPC)-管道 4、Linux系统编程系列之进程间通信-IPC对象 5、Linux系统…...

Linux CentOS7 vim多文件与多窗口操作

窗口是可视化的分割区域。Windows中窗口的概念与linux中基本相同。连接xshell就是在Windows中新建一个窗口。而vim打开一个文件默认创建一个窗口。同时&#xff0c;Vim打开一个文件也就会建立一个缓冲区&#xff0c;打开多个文件就会创建多个缓冲区。 本文讨论vim中打开多个文…...

SPI 通信协议

1. SPI通信 1. 什么是SPI通信协议 2. SPI的通信过程 在一开始会先把发送缓冲器的数据&#xff08;8位&#xff09;。一次性放到移位寄存器里。 移位寄存器会一位一位发送出去。但是要先放到锁存器里。然后从机来读取。从机的过程也一样。当移位寄存器的数据全部发送完。其实…...

【图像处理】使用各向异性滤波器和分割图像处理从MRI图像检测脑肿瘤(Matlab代码实现)

&#x1f4a5;&#x1f4a5;&#x1f49e;&#x1f49e;欢迎来到本博客❤️❤️&#x1f4a5;&#x1f4a5; &#x1f3c6;博主优势&#xff1a;&#x1f31e;&#x1f31e;&#x1f31e;博客内容尽量做到思维缜密&#xff0c;逻辑清晰&#xff0c;为了方便读者。 ⛳️座右铭&a…...

5个适合初学者的初级网络安全工作,网络安全就业必看

前言 网络安全涉及保护计算机系统、网络和数据免受未经授权的访问、破坏和盗窃 - 防止数字活动和数据访问的中断 - 同时也保护用户的资产和隐私。鉴于公共事业、医疗保健、金融以及联邦政府等行业的网络犯罪攻击不断升级&#xff0c;对网络专业人员的需求很高&#xff0c;这并…...

Kafka核心原理

1、Topic的分片和副本机制 分片作用&#xff1a; 解决单台节点容量有限的问题&#xff0c;节点多&#xff0c;效率提升&#xff0c;吞吐量提升。通过分片&#xff0c;将一个大的容器分解为多个小的容器&#xff0c;分布在不同的节点上&#xff0c;从而实现分布式存储。 分片…...

探秘前后端开发世界:猫头虎带你穿梭编程的繁忙街区,解锁全栈之路

&#x1f337;&#x1f341; 博主猫头虎 带您 Go to New World.✨&#x1f341; &#x1f984; 博客首页——猫头虎的博客&#x1f390; &#x1f433;《面试题大全专栏》 文章图文并茂&#x1f995;生动形象&#x1f996;简单易学&#xff01;欢迎大家来踩踩~&#x1f33a; &a…...

洛谷_分支循环

p2433 问题 5 甲列火车长 260 米&#xff0c;每秒行 12 米&#xff1b;乙列火车长220 米&#xff0c;每秒行 20 米&#xff0c;两车相向而行&#xff0c;从两车车头相遇时开始计时&#xff0c;多长时间后两车车尾相离&#xff1f;已知答案是整数。 计算方式&#xff1a;两车车…...

MySQL数据库入门到精通——进阶篇(3)

黑马程序员 MySQL数据库入门到精通——进阶篇&#xff08;3&#xff09; 1. 锁1.1 锁-介绍1.2 锁-全局锁1.3 锁-表级锁1.3.1 表级锁-表锁1.3.2 表级锁元数据锁( meta data lock&#xff0c;MDL)1.3.3 表级锁-意向锁1.3.4 表级锁意向锁测试 1.4 锁-行级锁1.4.1 行级锁-行锁1.4.2…...

Mind Map:大语言模型中的知识图谱提示激发思维图10.1+10.2

知识图谱提示激发思维图 摘要介绍相关工作方法第一步&#xff1a;证据图挖掘第二步&#xff1a;证据图聚合第三步&#xff1a;LLM Mind Map推理 实验实验设置医学问答长对话问题使用KG的部分知识生成深入分析 总结 摘要 LLM通常在吸收新知识的能力、generation of hallucinati…...

[引擎开发] 杂谈ue4中的Vulkan

接触Vulkan大概也有大半年&#xff0c;概述一下自己这段时间了解到的东西。本文实际上是杂谈性质而非综述性质&#xff0c;带有严重的主观认知&#xff0c;因此并没有那么严谨。 使用Vulkan会带来什么呢&#xff1f;简单来说就是对底层更好的控制。这意味着我们能够有更多的手段…...

docker--redis容器部署及地理空间API的使用示例-II

文章目录 Redis 地理位置类型API命令操作示例JAVA使用示例导入依赖RedisTemplate 操作GeoData示例CityInfo实体类Geo操作接口类Geo操作接口实现类SpringBoot测试类RedissonClient 操作GeoData示例docker–redis容器部署及与SpringBoot整合 docker–redis容器部署及地理空间API的…...

Vue中如何进行文件浏览与文件管理

Vue中的文件浏览与文件管理 文件浏览与文件管理是许多Web应用程序中常见的功能之一。在Vue.js中&#xff0c;您可以轻松地实现文件浏览和管理功能&#xff0c;使您的应用程序更具交互性和可用性。本文将向您展示如何使用Vue.js构建文件浏览器和文件管理功能&#xff0c;以及如…...

jenkins利用插件Active Choices Plug-in达到联动显示或隐藏参数,且参数值可修改

1. 添加组件 Active Choices Plug-in 如jenkins无法联网&#xff0c;可在以下两个地址中下载插件&#xff0c;然后放到/home/jenkins/.jenkins/plugin下面重启jenkins即可 Active Choices Active Choices | Jenkins plugin 2. 效果如下&#xff1a; sharding为空时&#xf…...

香蕉叶病害数据集

1.数据集 第一个文件夹为数据增强&#xff08;旋转平移裁剪等操作&#xff09;后的数据集 第二个文件夹为原始数据集 2.原始数据集 Cordana文件夹&#xff08;162张照片&#xff09; healthy文件夹&#xff08;129张&#xff09; Pestalotiopsis文件夹&#xff08;173张照片&…...

天地无用 - 修改朋友圈的定位: 高德地图 + 爱思助手

1&#xff0c;电脑上打开高德地图网页版 高德地图 (amap.com) 2&#xff0c;网页最下一栏&#xff0c;点击“开放平台” 高德开放平台 | 高德地图API (amap.com) 3&#xff0c;在新网页中&#xff0c;需要登录高德账户才能操作。 可以使用手机号和验证码登录。 4&#xff0c…...

AtCoder Beginner Contest 232(A-G)

A - QQ solver (atcoder.jp)直接按题意模拟即可。 B - Caesar Cipher (atcoder.jp)按题意模拟即可 C - Graph Isomorphism (atcoder.jp)按题意模拟即可 D - Weak Takahashi (atcoder.jp) 一个非常套路的网格dp E - Rook Path (atcoder.jp) &#xff08;1&#xff09;题意 有…...

计算机网络(第8版)-第5章 运输层

5.1 运输层协议概述 5.1.1 进程之间的通信 图5-1 中两个运输层之间有一个深色双向粗箭头&#xff0c;写明“运输层提供应用进程间的逻辑通信”。 图5-1 运输层为相互通信的应用进程提供了逻辑通信 5.1.2 运输层的两个主要协议 5.1.3 运输层的端口 请注意&#xff0c;这种…...

AtCoder Beginner Contest 231(D-F,H)

D - Neighbors (atcoder.jp) &#xff08;1&#xff09;题意 给出M组关系&#xff0c;问是否有一个排列&#xff0c;能表示A[i]和B[i]相邻 &#xff08;2&#xff09;思路 考虑如果有环&#xff0c;显然不能满足排列&#xff0c;因为排列中度数最多为2&#xff0c;若有超过2的显…...

个人计算机做服务器建网站/南昌seo快速排名

Fast RCNN训练自己的数据集 (2修改读写接口)这里楼主讲解了如何修改Fast RCNN训练自己的数据集&#xff0c;首先请确保你已经安装好了Fast RCNN的环境&#xff0c;具体的编配编制操作请参考我的上一篇文章。首先可以看到fast rcnn的工程目录下有个Lib目录这里下面存在3个目录分…...

个人网站模板html代码/如何免费做网站网页

事件对象 每个事件处理函数都会获得一个事件对象&#xff0c;该对象中包含和此事件相关的方法及属性。 事件对象在事件触发时自动传入。 事件对象的属性有&#xff1a; type&#xff1a;事件类型&#xff0c;如click、mouseover等 which&#xff1a;被按下的按钮或键 data&…...

网站建设小技巧/推广普通话宣传语100字

Web3——互联网发展的“下一阶段”&#xff0c;预计它将以区块链技术为基础。在所有定义Web3的说法中&#xff0c;也许没有一个比去中心化更重要或普遍。虽然加密货币处于这场运动的最前沿&#xff0c;但科技行业的一些人认为&#xff0c;去中心化是互联网不可避免的进化步骤&a…...

江西做网站找谁/中国刚刚发生8件大事

关于SDK-gcc在Linux系统下的环境搭建如有不足欢迎补充与完善1、首先打开官方提供的SDK—gcc目录&#xff0c;如图1&#xff1a;图1其中readme.txt文件是对整个目录文件的说明&#xff0c;如图2&#xff1a;图22、关于readme.txt中&#xff0c;第一点和第四点作一下说明&#xf…...

网页制作与网站建设题/公众号运营收费价格表

职工管理项目模型在编程作业随处可见&#xff0c;如【学生信息管理系统】、【图书馆管理系统】等等 这里给出【IT公司职工管理系统】的实现&#x1f447; 系统要求描述&#xff1a; 有一家小小的IT公司&#xff0c;只有三类员工&#xff1a;普通程序员、项目经理、公司董事&am…...

做煤网站/网络营销策划方案的目的

题图摄于上海世博会关注 亨利笔记 公众号&#xff0c;回复 GOTC &#xff0c;可下载中国首个原创 CNCF 项目 Harbor 在 GOTC 大会上的演讲ppt 。 7 月 10 日&#xff0c;「GOTC 全球开源技术峰会“开源云原生计算时代论坛”」在上海世博中心召开。大会包含多个主题分论坛&#…...