【矩阵快速幂】封装类及测试用例及样例

2024-01-15 08:20

本文主要是介绍【矩阵快速幂】封装类及测试用例及样例,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

作者推荐

视频算法专题

通俗的说,就是矩阵的乘方。

封装类

核心代码

class CMat
{
public:// 矩阵乘法static vector<vector<long long>> multiply(const vector<vector<long long>>& a, const vector<vector<long long>>& b) {const int r = a.size(), c = b.front().size(),iK = a.front().size();assert(iK == b.size());vector<vector<long long>> ret(r, vector<long long>(c));for (int i = 0; i < r; i++){for (int j = 0; j < c ; j++) {for (int k = 0; k < iK; k++){ret[i][j] = (ret[i][j] + a[i][k] * b[k][j] ) % s_llMod;}}}return ret;}// 矩阵快速幂static vector<vector<long long>> pow( const vector<vector<long long>>& a, vector<vector<long long>> b, long long n) {vector<vector<long long>> res = a;for (; n; n /= 2) {if (n % 2) {res = multiply(res, b);}b = multiply(b, b);}return res;}static vector<vector<long long>> TotalRow(const vector<vector<long long>>& a){vector<vector<long long>> b(a.front().size(), vector<long long>(1, 1));return multiply(a, b);}
protected:const static long long s_llMod = 1e9 + 7;
};

测试用例

template<class T>
void Assert(const T& t1, const T& t2)
{assert(t1 == t2);
}template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{if (v1.size() != v2.size()){assert(false);return;}for (int i = 0; i < v1.size(); i++){Assert(v1[i], v2[i]);}
}int main()
{vector<vector<long long>> pre = { {1,2} };vector<vector<long long>> mat = { {2,3},{1,10} };{	auto res = CMat::pow(pre, mat, 0);Assert(pre, res);}{auto res = CMat::multiply(pre, mat);Assert(vector<vector<long long>>{ {4, 23}}, res);auto res2 = CMat::pow(pre, mat,1);Assert(res2, res);}{auto res = CMat::pow(pre, mat, 2);auto res1 = CMat::multiply(pre, mat);auto res2 = CMat::multiply(res1, mat);Assert(res2, res);Assert(vector<vector<long long>>{ {31, 242}}, res);};for (int i = 3; i < 100; i++){auto res = pre;for (int j = 0; j < i; j++){res = CMat::multiply(res, mat);}auto res2 = CMat::pow(pre, mat, i);Assert(res2, res);}}

具体例子

题目、分析和原理见:

【动态规划】【矩阵快速幂】【滚动向量】C++算法552. 学生出勤记录 II

原解法用二维表示状态,改成一维。 i是缺勤数量,j是连续迟到数,新的状态为:3*i+j
6种状态,故转移矩阵为6行6列,故结果矩阵为6列,6个数据1行就足够了。
令旧结果矩阵为mat1,转移矩阵为mat2,新矩阵为mat3,K mat1的列数,mat2的行数。则:
mat3[r][c] = Sum [ 0 , k ) i ^{i}_{[0,k)} [0,k)i(mat1[r][i]*mat2[i][c])

i在mat1中列号,在mat2中是行号。 也就是旧状态在第几列,mat2就在第几行。
新状态就是mat2的行号。

class Solution {
public:int checkRecord(int n) {vector<vector<long long>> pre(1, vector<long long>(6));//1行6列	pre[0][0] = 1;vector<vector<long long>> mat(6, vector<long long>(6));{	//之前的状态在pre是第几列,矩阵中就是第几行。新状态的列号就矩阵的列号//处理一次缺勤 ,缺勤两次排除for (int i = 0; i < 3; i++){mat[i][3]++;}//处理请假for (int i = 0; i < 2; i++){for (int j = 0; j < 2; j++){const int pre = 3 * i + j;mat[pre][pre + 1]++;}}//处理正常for (int i = 0; i < 2; i++){for (int j = 0; j < 3; j++){const int pre = 3 * i + j;const int cur = 3 * i;mat[pre][cur]++;}}}auto res = CMat::pow(pre, mat, n);res = CMat::TotalRow(res);return res[0][0];}
};

测试用例

template
void Assert(const T& t1, const T& t2)
{
assert(t1 == t2);
}

template
void Assert(const vector& v1, const vector& v2)
{
if (v1.size() != v2.size())
{
assert(false);
return;
}
for (int i = 0; i < v1.size(); i++)
{
Assert(v1[i], v2[i]);
}
}

int main()
{
int n;
{
Solution sln;
n = 0;
auto res = sln.checkRecord(n);
Assert(1, res);
}
{
Solution sln;
n = 1;
auto res = sln.checkRecord(n);
Assert(3, res);
}
{
Solution sln;
n = 2;
auto res = sln.checkRecord(n);
Assert(8, res);
}
{
Solution sln;
n = 3;
auto res = sln.checkRecord(n);
Assert(19, res);
}
{
Solution sln;
n = 4;
auto res = sln.checkRecord(n);
Assert(43, res);
}
{
Solution sln;
n = 5;
auto res = sln.checkRecord(n);
Assert(94, res);
}
{
Solution sln;
n = 6;
auto res = sln.checkRecord(n);
Assert(200, res);
}
{
Solution sln;
n = 7;
auto res = sln.checkRecord(n);
Assert(418, res);
}
{
Solution sln;
n = 10101;
auto res = sln.checkRecord(n);
Assert(183236316, res);
}
}

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快

速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关

下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 **C+

+17**
如无特殊说明,本算法用**C++**实现。

这篇关于【矩阵快速幂】封装类及测试用例及样例的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/608244

相关文章

springboot security快速使用示例详解

《springbootsecurity快速使用示例详解》:本文主要介绍springbootsecurity快速使用示例,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝... 目录创www.chinasem.cn建spring boot项目生成脚手架配置依赖接口示例代码项目结构启用s

SpringBoot中封装Cors自动配置方式

《SpringBoot中封装Cors自动配置方式》:本文主要介绍SpringBoot中封装Cors自动配置方式,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录SpringBoot封装Cors自动配置背景实现步骤1. 创建 GlobalCorsProperties

Java导入、导出excel用法步骤保姆级教程(附封装好的工具类)

《Java导入、导出excel用法步骤保姆级教程(附封装好的工具类)》:本文主要介绍Java导入、导出excel的相关资料,讲解了使用Java和ApachePOI库将数据导出为Excel文件,包括... 目录前言一、引入Apache POI依赖二、用法&步骤2.1 创建Excel的元素2.3 样式和字体2.

C++快速排序超详细讲解

《C++快速排序超详细讲解》快速排序是一种高效的排序算法,通过分治法将数组划分为两部分,递归排序,直到整个数组有序,通过代码解析和示例,详细解释了快速排序的工作原理和实现过程,需要的朋友可以参考下... 目录一、快速排序原理二、快速排序标准代码三、代码解析四、使用while循环的快速排序1.代码代码1.由快

JAVA封装多线程实现的方式及原理

《JAVA封装多线程实现的方式及原理》:本文主要介绍Java中封装多线程的原理和常见方式,通过封装可以简化多线程的使用,提高安全性,并增强代码的可维护性和可扩展性,需要的朋友可以参考下... 目录前言一、封装的目标二、常见的封装方式及原理总结前言在 Java 中,封装多线程的原理主要围绕着将多线程相关的操

Win32下C++实现快速获取硬盘分区信息

《Win32下C++实现快速获取硬盘分区信息》这篇文章主要为大家详细介绍了Win32下C++如何实现快速获取硬盘分区信息,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 实现代码CDiskDriveUtils.h#pragma once #include <wtypesbase

Spring AI与DeepSeek实战一之快速打造智能对话应用

《SpringAI与DeepSeek实战一之快速打造智能对话应用》本文详细介绍了如何通过SpringAI框架集成DeepSeek大模型,实现普通对话和流式对话功能,步骤包括申请API-KEY、项目搭... 目录一、概述二、申请DeepSeek的API-KEY三、项目搭建3.1. 开发环境要求3.2. mav

Python如何快速下载依赖

《Python如何快速下载依赖》本文介绍了四种在Python中快速下载依赖的方法,包括使用国内镜像源、开启pip并发下载功能、使用pipreqs批量下载项目依赖以及使用conda管理依赖,通过这些方法... 目录python快速下载依赖1. 使用国内镜像源临时使用镜像源永久配置镜像源2. 使用 pip 的并

SpringBoot快速接入OpenAI大模型的方法(JDK8)

《SpringBoot快速接入OpenAI大模型的方法(JDK8)》本文介绍了如何使用AI4J快速接入OpenAI大模型,并展示了如何实现流式与非流式的输出,以及对函数调用的使用,AI4J支持JDK8... 目录使用AI4J快速接入OpenAI大模型介绍AI4J-github快速使用创建SpringBoot

使用Python快速实现链接转word文档

《使用Python快速实现链接转word文档》这篇文章主要为大家详细介绍了如何使用Python快速实现链接转word文档功能,文中的示例代码讲解详细,感兴趣的小伙伴可以跟随小编一起学习一下... 演示代码展示from newspaper import Articlefrom docx import