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

矩阵快速幂快速求解递推公式

news 来源：原创 2025/8/23 13:09:00

文章目录

习题
- 790.多米诺和托米诺平铺

对于一个给定的递推公式，例如dp[i] = dp[i-1] * a + dp[i-2] * b,那么常用的做法，肯定是使用o(n)的时间复杂度进行线性求解，但是如果 $n={10}^{18}$ ，那么肯定超时的，这个时候就需要使用到矩阵快速幂，其实也就是使用矩阵运算+快速幂进行求解递归结果

矩阵乘法

咱们先手搓一下矩阵乘法！
这是一个 $o(n^3)$ 时间复杂度的暴力做法，那么如何快速记忆？
- 矩阵A和B的形状分别是a*b和b*c，结果矩阵C的形状是a*c，所以最外层循环是rang(a)，中间一层的循环是range(c)，最内层循环是range(b)，最内层循环用于将矩阵A和B对应位置的元素相乘再进行求和

# 矩阵乘法 A @ B
def matrix_multiply(A, B):m, n = len(A), len(B[0])C = [[0] * n for _ in range(m)]for i in range(m):for j in range(n):for k in range(len(B)):C[i][j] += A[i][k] * B[k][j]return C

快速幂

快速幂是一种思想！将幂次的指数进行二分拆解，在o(logn)时间复杂度内求解出幂次，而不在乎底的形式(正常来说就是数，在这里就替换成矩阵！不过无所谓只要能乘起来即可)

# 矩阵快速幂，A ^ n @ B ,用于求解 矩阵 A 的 n 次幂，然后再乘上 矩阵 B
# 矩阵快速幂 求解A ^ n * B 
def matrix_power(A, n, B):res = B while n > 0:if n & 1:res = matrix_multiply(res, A)A = matrix_multiply(A, A)n >>= 1return res

习题

对于习题，其实只要是递推公式，都可以使用矩阵快速幂来快速求解，当然这也是当n>10^7左右的时候，使用线性时间会超时的情况

790.多米诺和托米诺平铺

在这里插入图片描述

思路分析：上面的题目的递推公式比较难想，建议可以去看灵神的题解，这里主要是使用这个题目作为例子，说明矩阵快速幂的使用

灵神题解

递推公式f[i] = f[i - 1] * 2 + f[i - 3]
根据等式右边，涉及到f[i-1]和f[i-3],虽然没有涉及f[i-2]，所以右边设置为3*1的矩阵，左边的话，为了对应也设置一个3*1的矩阵

在这里插入图片描述

然后根据这个递推公式确定权重矩阵A

在这里插入图片描述

MOD = 1_000_000_007# a @ b，其中 @ 是矩阵乘法
def mul(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:return [[sum(x * y for x, y in zip(row, col)) % MOD for col in zip(*b)]for row in a]# a^n @ f
def pow_mul(a: List[List[int]], n: int, f: List[List[int]]) -> List[List[int]]:res = fwhile n:if n & 1:res = mul(a, res)a = mul(a, a)n >>= 1return resclass Solution:def numTilings(self, n: int) -> int:if n == 1:return 1f2 = [[2], [1], [1]]m = [[2, 0, 1], [1, 0, 0], [0, 1, 0]]fn = pow_mul(m, n - 2, f2)return fn[0][0]

矩阵快速幂快速求解递推公式

文章目录习题790.多米诺和托米诺平铺对于一个给定的递推公式，例如dp[i] dp[i-1] * a dp[i-2] * b,那么常用的做法，肯定是使用o(n)的时间复杂度进行线性求解，但是如果 n 10 18 n{10}^{18} n1018，那么肯定超时的，这…...

编程日记 2025/8/23 13:09:00

驱动开发硬核特训 · Day 28（上篇）：pinctrl 子系统详解与实战分析

📅 日期：2025-05-05 📚 技术平台：嵌入式Jerry（B站） 一、引言在嵌入式系统中，SoC 芯片的引脚通常具有多种功能，如 GPIO、UART、I2C、SPI 等。为了在不同的应用场景中灵活配置引脚功…...

编程日记 2025/8/24 9:06:11

20250505下载VLC for Android

20250505下载VLC for Android 2025/5/5 14:35 缘起：做Rockchip的RK3566的Android13下的跨网段PING。酷芯的图传网段和 softAP/以太网RJ45共享网段之间互相PING通。图传的原厂/供应商说可以使用ffmpeg进行rtsp流的转发。后来确认VLC for Android版本只有接受流&a…...

编程日记 2025/8/24 9:06:51

Jetpack Compose 响应式布局实战：BoxWithConstraints 完全指南

深入理解 Jetpack Compose 中的 BoxWithConstraints 前言在构建现代 Android 应用时，响应式设计已成为必不可少的要求。Jetpack Compose 作为 Android 的现代 UI 工具包，提供了 BoxWithConstraints 这一强大组件，帮助我们轻松创建能够适应…...

编程日记 2025/8/23 2:30:34

ZYNQ笔记（十七）：IP核封装与接口定义

版本：Vivado2020.2（Vitis） 任务：将“HDMI彩条显示实验”（正点原子 ZYNQ FPGA 开发视频）中所实现的 RGB2DVI 模块封装成一个 IP 核。目录一、介绍 （1）IP核 （2&#x…...

编程日记 2025/8/24 9:08:05

学习笔记msp430f5529lp

注：本文仅用于个人学习使用，记录笔记。学习视频msp430f5529库函数入门教程 00.序言_哔哩哔哩_bilibili 向大佬致敬理工男小帅-CSDN博客 CCS环境快捷键使用代码注释：Ctrl/ 提示/补全: CtrlShiftC 放大:Ctrl 缩小:Ctrl- 切换选择模式&…...

编程日记 2025/8/21 12:45:03

人工智能应用：从技术突破到生态重构的演进之路

一、人工智能的发展历程：从符号主义到通用智能探索人工智能（AI）的发展始于20世纪中叶，其历程可划分为四个关键阶段： 符号主义与早期探索（1950s-1970s） 以逻辑推理和专家系统为核心&…...

编程日记 2025/8/23 1:06:08

【ZYNQ Linux移植】4-内核移植

文章目录 0 写在前面1 内核源码的文件结构2 Linux内核移植2.1 移植配置文件2.2 移植设备树2.3 创建脚本进行编译2.4 备份相关文件 3 测试4 总结5 参考资料 0 写在前面这是一个系列博客，详细介绍如何在 ZYNQ 与 ZYNQ MP 平台上如何移植 Linux 系统。目前网络上的大部…...

编程日记 2025/8/23 5:48:46

代码随想录算法训练营第三十二天

LeetCode/卡码网题目: 518. 零钱兑换 II377. 组合总和 Ⅳ790. 多米诺和托米诺平铺(每日一题)57. 爬楼梯（第八期模拟笔试） 其他: 今日总结往期打卡背包问题特点: 滚动数组背包遍历顺序完全背包从小到大,即基于当前物品更新过的继续更新01背包从大到…...

编程日记 2025/8/21 12:44:57

java CompletableFuture 异步编程工具用法1

1、测试异步调用： static void testCompletableFuture1() throws ExecutionException, InterruptedException {// 1、无返回值的异步任务。异步线程执行RunnableCompletableFuture.runAsync(() -> System.out.println("only you"));// 2、有返回值的异…...

编程日记 2025/8/21 12:44:55

Spring Boot 集成 Solr 的详细步骤及示例

环境准备安装 Solr ：从 Solr 官网（Welcome to Apache Solr - Apache Solr）下载并安装最新版本，然后通过命令 bin/solr start 启动 Solr 服务，使用 bin/solr create -c mycore 创建一个新的 Solr 核心。安装 JDK &am…...

编程日记 2025/8/21 11:42:59

Nemotron-Research-Tool-N1 如何提升大语言模型工具使用能力？

Nemotron-Research-Tool-N1如何提升大语言模型工具使用能力？ 如今，大语言模型（LLMs）发展迅猛，给它配备外部工具成为研究热点。但传统方法存在不少问题。这篇论文提出的Nemotron-Research-Tool-N1系列模型带来新突破&a…...

编程日记 2025/8/21 12:44:51

OpenCV进阶操作：图像直方图、直方图均衡化

文章目录一、图像直方图二、图像直方图的作用三、使用matplotlib方法绘制直方图2.使用opencv的方法绘制直方图（划分16个小的子亮度区间）3、绘制彩色图像的直方图四、直方图均衡化1、绘制原图的直方图2、绘制经过直方图均衡化后的图片的直方图3、自适应…...

编程日记 2025/8/21 12:44:48

Android控件VideoView用法

一控件UI <VideoViewandroid:id="@+id/videoView"android:layout_width="match_parent"android:layout_height="match_parent"android:scaleType="fitCenter" /> 二配置 <?xml version="1.0" encoding="u…...

编程日记 2025/8/21 2:30:01

人工智能数学基础（十）—— 图论

图论作为数学的重要分支，为人工智能提供了强大的建模和分析工具。无论是社交网络分析、路径规划还是数据结构设计，图论都发挥着不可替代的作用。今天，我将带领大家深入浅出地探索图论的核心概念，并结合 Python 实例，让…...

编程日记 2025/8/20 14:20:45

深入探索Anthropic Claude与Spring AI的融合应用

深入探索Anthropic Claude与Spring AI的融合应用前言在人工智能的蓬勃发展进程中，自然语言处理领域不断涌现出强大的模型和工具。Anthropic Claude系列基础AI模型凭借其出色的性能，在各种应用场景中展现出巨大潜力，为开发者和企业提供了丰…...

编程日记 2025/8/24 8:43:24

Python爬虫实战：获取优美图库各类高清图片，为用户提供设计素材

一、引言在互联网时代，高清壁纸资源丰富多样，而优美图库作为一个提供大量精美壁纸的网站，吸引了众多用户。通过 Python 爬虫技术，可以自动化地从该网站获取所需的壁纸资源，为用户节省时间和精力。然而，网站通常会采取反爬措施来防止数据被恶意抓取，因此需要在爬虫程序…...

编程日记 2025/8/21 12:44:40

Java常用注解大全（基于JDK17+SpringBoot3）

一、基础注解（Java原生）编译相关 @Override：方法重写校验 java 复制下载 @Override public String toString() { return "CustomObj"; } @Deprecated：标记过时元素 java 复制下载 @Deprecated(since="1.8", forRemoval=true) public void oldMethod…...

编程日记 2025/8/21 13:34:34

【NLP】30. 深入理解 In-Context Learning 的核心机制与策略

In-Context Learning（ICL）详解：提示学习时代的语言理解一、什么是 In-Context Learning（ICL）？ In-Context Learning 是指： 不改变模型参数，通过在输入中加入示例（demon…...

编程日记 2025/8/17 8:42:59

数字化工厂中央控制室驾驶舱系统 - Windows 部署笔记

数字化工厂中央控制室驾驶舱系统 - Windows 部署笔记环境准备这篇笔记记录了我在 Windows 10/11 上部署数字化工厂中央控制室驾驶舱系统的全过程，包括各种常见问题的解决方法。部署过程中使用了国内镜像源来加快下载速度。前置需求 Python：3.8 到…...

编程日记 2025/8/21 12:44:38

数据库的原子事务

原子事务 11.1 全有或全无效应二级索引需要原子性的多键更新，这不仅对数据库内部一致性至关重要，也对应用数据的一致性非常有用（例如考虑账户余额和账户交易）。我们将放弃get-set-del接口，并添加一个新的接口来允…...

编程日记 2025/8/23 2:30:21

基于51单片机的红外人体感应报警器

基于51单片机的人体监测报警 （仿真＋程序＋原理图＋PCB） 功能介绍具体功能： 1.按下报警按钮会发生红LED蜂鸣器声光报警； 2.若检测到人，黄LED打开； 3.按下布防按键&…...

编程日记 2025/8/21 13:34:30

从Excel到高级工具：数据分析进阶指南

从Excel到高级工具：数据分析进阶指南在数据分析的世界里，Excel曾经是众多人的第一站。它简单、直观、功能强大，从普通用户到专业人士，无不对其依赖。然而，随着数据规模增长、分析需求升级，Excel渐渐显得力…...

编程日记 2025/8/21 12:33:55

Excel VBA 自定义函数

一、VBA 函数基础概念在 Excel VBA 中，函数主要分为两种类型： Sub 过程：执行操作但不返回值Function 函数：执行操作并返回结果基本语法示例 1. Function 函数示例定义一个返回字符串的公共函数 Public Function GetGreetin…...

编程日记 2025/8/20 15:59:23

004-nlohmann/json 快速认识-C++开源库108杰

了解 nlohmann/json 的特点；理解编程中 “数据战场”划分的概念；迅速上手多种方式构建一个JSON对象； 1 特点与安装 nlohmann/json 是一个在 github 长期霸占 “JSON” 热搜版第1的CJSON处理库。它的最大优点是与 C 标准库的容器数据&#xf…...

编程日记 2025/8/24 5:38:15

【Quest开发】接入语音转文字

参考官方文档：https://developers.meta.com/horizon/documentation/unity/voice-sdk-tutorials-overview 软件：Unity 2022.3.51f1c1、vscode、Meta XR All in One SDK V72 硬件：Meta Quest3 注意：需全程科学上网 Meta提供了一…...

编程日记 2025/8/21 14:47:31

Vim 命令从头学习记录

学习链接：eleon-vim基础教程 Vim - 基础翻屏操作光标移动：hjkl 20j 向下移动20行，w 向后移动一个字符，b 向前移动一个字符。 Ctrl u 向上翻半页 UP Ctrl d 向下翻半页 Down Ctrl f 向下翻整页 Forward Ctrl b 向上翻整页 …...

编程日记 2025/8/21 6:19:44

[Linux]物理地址到虚拟地址的转化

[Linux]物理地址到虚拟地址的转化水墨不写bug 文章目录一、再次认识地址空间二、页表1、页表的结构设计2、页表节省了空间，省在哪里？3、页表的物理实现一、再次认识地址空间 OS和磁盘交互的内存基本单位是4KB，这4KB通常被称为内存块。OS对…...

编程日记 2025/8/22 21:43:07

js获取明天日期、Vue3大菠萝 Pinia的使用

直接上代码 const today new Date(2019, 2, 28) const finalDate new Date(today) finalDate.setDate(today.getDate() 3)console.log(finalDate) // 31 March 2019 安装 yarn add pinia # or with npm npm install pinia创建第一个store仓库 1、在src目录下创建store目录…...

编程日记 2025/8/21 14:47:29

矩阵置零（中等）

可以用两个标记数组分别记录每一行和每一列是否有零出现。首先遍历该数组一次，如果某个元素为 0，那么就将该元素所在的行和列所对应标记数组的位置置为 true。然后再次遍历该数组，用标记数组更新原数组。 class Solution {public void set…...

编程日记 2025/8/22 18:49:53

GZ人博会自然资源系统（测绘）备考笔记

本文为备考 GZ人才博览会自然资源系统（测绘） 的笔记，包括若干知识点整理及近两年考核（面试）真题 （文末附《GZ人博会自然资源系统（测绘）备考笔记》1 的下载链接）。目录…...

编程日记 2025/8/21 14:47:25

《进制转换的终极指南：原理、方法与编程应用》

🚀个人主页：BabyZZの秘密日记 📖收入专栏：C语言 🌍文章目入一、进制转换的基本原理二、进制转换方法总结（一）使用权重法的转换1. 二进制 → 十进制2. 八进制 → 十进制3. 十六进制 → 十进制 &…...

编程日记 2025/8/21 14:47:23

2025系统架构师---论软件的设计模式论文

2023 年，我所在的公司承担了某部网络靶场的研发任务。我作为公司的技术总监，希望能打造基于网络靶场的系列产品，参与到项目的设计中，以期开发扩展性和可维护性良好的网络靶场，为以后的产品开发打下基础。网络靶场是网络安全技术研究的基础支撑平台，它利用虚拟的和实物…...

编程日记 2025/8/21 14:47:21

嵌入式Linux驱动学习

Ubuntu18 下载链接 https://releases.ubuntu.com/bionic/ Ubuntu配置静态IP 更新Ubuntu18的镜像源以清华大学镜像源举例网站：https://mirrors.tuna.tsinghua.edu.cn/ 第一步点开网站搜索ubuntu然后点击问号第二步选择自己的Ubuntu版本第三步在Ubuntu中复制…...

编程日记 2025/8/21 6:08:29

基于大模型的子宫腺肌病全流程预测与诊疗方案研究报告

目录一、引言 1.1 研究背景与意义 1.2 研究目的与创新点二、子宫腺肌病概述 2.1 疾病定义与病理机制 2.2 流行病学特征 2.3 现有诊断与治疗方法综述三、大模型技术原理与应用基础 3.1 大模型简介 3.2 在医疗领域的应用现状 3.3 适用于子宫腺肌病预测的可行性分析…...

编程日记 2025/8/21 14:47:17

Notebook.ai 开源程序是一套工具，供作家、游戏设计师和角色扮演者创建宏伟的宇宙 - 以及其中的一切

一、软件介绍文末提供程序和源码下载 Notebook.ai 开源程序是一套工具，供作家、游戏设计师和角色扮演者创建宏伟的宇宙 - 以及其中的一切。二、软件特点 Notebook 是作家的规划工具，用于创建从宇宙到角色、情节到单个项目的任何内容。通过浏览器、…...

编程日记 2025/8/21 14:47:15

关于 dex2oat 以及 vdex、cdex、dex 格式转换

版权归作者所有，如有转发，请注明文章出处：https://cyrus-studio.github.io/blog/ dex2oat dex2oat 是 Android 系统中的一个核心工具，负责将应用中的 .dex（Dalvik Executable）字节码编译为本地机器代码&am…...

编程日记 2025/8/21 14:47:13

Java---Object和内部类

Object类和内部类前言：一、Object类1.object类初识2.Object的方法2.(1).获取对象的信息--toString方法2.(2).对象比较equals方法2.(3).hashCode方法二、内部类1.内部类初识：2.内部类的分类：2.(1).实例内部类2.(2).静态内部类2.(3).匿名内部…...

编程日记 2025/8/21 14:47:11

【OSPF协议深度解析】从原理到企业级网络部署

目录前言技术背景与价值当前技术痛点解决方案概述目标读者说明一、技术原理剖析核心概念图解核心作用讲解关键技术模块说明技术选型对比二、实战演示环境配置要求核心配置实现案例1：单区域基础配置案例2：多区域配置案例3：安全认证配置运行…...

编程日记 2025/8/21 14:47:09

linux tar命令详解。压缩格式对比

1.压缩格式对比压缩格式命令选项文件扩展名压缩率速度无压缩-cvf.tar无最快gzip-czvf.tar.gz中等较快bzip2-cjvf.tar.bz2较高较慢xz-cJvf.tar.xz最高最慢 9. 更多参考【Linux基础】文件压缩tar命令指南tar压缩方式对比...

编程日记 2025/8/21 13:34:27

C++和Lua混和调用

为什么要C/C 流行的语言，学习人员多高性能，对于嵌入式设备则是省电大量的第三方库为什么要Lua C缺点：编译慢，调试难，学习难度大Lua优点： 最快的脚本语言可以编译调试与C/C结合容易Lua是对性能有要求的必…...

编程日记 2025/8/21 14:47:07

Cadence高速系统设计流程及工具使用

上一章已经谈到，在Cadence的高速设计流程中，有两个重要的工具SigXP和Constrain Manager（CM约束管理器）。SigXP是仿真分析工具和约束生成工具，我们就是使用这个工具对关键信号进行仿真的。SI工程师通过对仿真结果的分析…...

编程日记 2025/8/21 14:47:05

Unity：AddTorque()（增加旋转力矩）

目录什么是 AddTorque()？ 第一性原理出发：什么是 Torque（力矩）？ Torque 公式 Unity 中 AddTorque 的工作原理参数属性 🔍 Linear Drag（线性阻力） 线性阻力模拟的现实情况&…...

编程日记 2025/8/21 14:47:03

嵌入式硬件设计全解析：从架构到实战

一、嵌入式硬件设计核心架构与系统组成 1. 处理器选型与架构设计（1）处理器类型与应用场景处理器类型代表架构 / 型号典型应用场景核心优势微控制器（MCU） ARM Cortex-M3/M4、STM32F 系列低功耗控制、小型设备集成外设、低功耗、低成本微处…...

编程日记 2025/8/21 3:22:45

R7打卡——糖尿病预测模型优化探索

🍨 本文为🔗365天深度学习训练营中的学习记录博客 🍖 原作者：K同学啊 1.检查GPU import torch.nn as nn import torch.nn.functional as F import torchvision,torch# 设置硬件设备，如果有GPU则使用，没有…...

编程日记 2025/8/23 23:11:07

win10开了移动热点，手机无法连接，解决办法（chatgpt版）

提问： win10连着网线上网，有无线网卡intel Wireless-AC 9560网卡可以用电脑开移动热点给手机连接吗？如何设置？我现在可以开热点，但是手机连不上，显示正在获取ip地址后就连不上了 chatgpt回答&#xff1a…...

编程日记 2025/8/23 13:22:11

下载core5compat 模块时，被禁止，显示 - servese replied: Forbbidden. --＞换镜像源

怎么解决？ --->换镜像源方法 1：使用命令行参数指定镜像源在运行 Qt 安装器时，通过 --mirror 参数指定镜像源： # Windows qt-unified-windows-x64-online.exe --mirror https://mirrors.ustc.edu.cn/qtproject# Linux/macO…...

编程日记 2025/8/21 14:46:55

《MATLAB实战训练营：从入门到工业级应用》高阶挑战篇-《用无人机仿真玩转PID控制：MATLAB四旋翼仿真建模全攻略》

《MATLAB实战训练营：从入门到工业级应用》高阶挑战篇-✈️ 用无人机仿真玩转PID控制：MATLAB四旋翼仿真建模全攻略 🚁 欢迎来到这篇超级详细的MATLAB四旋翼无人机仿真教程！无论你是控制理论爱好者、无人机发烧友，还是M…...

编程日记 2025/8/21 14:46:52

GESP2024年3月认证C++八级( 第二部分判断题（1-5））

孙子定理参考程序： #include <iostream> #include <vector> using namespace std;// 扩展欧几里得算法：用于求逆元 int extendedGCD(int a, int b, int &x, int &y) {if (b 0) {x 1; y 0;return a;}int x1, y1;int gcd extende…...

编程日记 2025/8/21 14:46:50

PHP的现代复兴：从脚本语言到企业级服务端引擎的演进之路-优雅草卓伊凡

PHP的现代复兴：从脚本语言到企业级服务端引擎的演进之路-优雅草卓伊凡一、PHP的历史误解与现实真相 1.1 被固化的陈旧认知当卓伊凡浏览知乎上关于PHP的讨论时，发现大量回答仍然停留在十年前的刻板印象中。这些误解包括但不限于： “PHP只…...

编程日记 2025/8/23 17:17:53

文章目录

习题

790.多米诺和托米诺平铺

相关文章：