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

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

封装类

核心代码

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++**实现。

相关文章
|
17天前
|
消息中间件 Java 数据库
【消息队列开发】 实现 VirtualHostTests 类——测试虚拟主机操作
【消息队列开发】 实现 VirtualHostTests 类——测试虚拟主机操作
|
17天前
|
消息中间件 存储 测试技术
【消息队列开发】 实现MemoryDataCenterTests类——测试管理内存数据
【消息队列开发】 实现MemoryDataCenterTests类——测试管理内存数据
|
8天前
|
JavaScript Java 测试技术
《手把手教你》系列技巧篇(七十一)-java+ selenium自动化测试-自定义类解决元素同步问题(详解教程)
【6月更文挑战第12天】本文介绍了如何创建一个自定义类库来解决自动化测试中的元素同步问题。作者指出,大部分错误源于元素因时间不同步而引发,为此提供了一种解决方案。在项目实践中,首先在`library`包下创建名为`MyWait`的类,包含一个方法`isElementPresent`,该方法通过循环尝试并等待指定元素出现,避免了直接使用时间等待可能导致的不准确性。之后,在测试类中调用此自定义方法,成功实现了元素同步。代码示例展示了如何在Java+Selenium自动化测试中应用这个自定义类。
28 2
|
14天前
|
Java 测试技术
测试类基础
测试类基础
10 1
|
17天前
|
消息中间件 Java 测试技术
【消息队列开发】 测试MessageFileManager(对硬盘中的消息操作)类
【消息队列开发】 测试MessageFileManager(对硬盘中的消息操作)类
|
17天前
|
消息中间件 API
【消息队列开发】 实现 MqClientTests 类——测试客户端
【消息队列开发】 实现 MqClientTests 类——测试客户端
|
1月前
|
安全 Java 测试技术
Spring Boot 自动化单元测试类的编写过程
企业开发不仅要保障业务层与数据层的功能安全有效,也要保障表现层的功能正常。但是我们一般对表现层的测试都是通过postman手工测试的,并没有在打包过程中代码体现表现层功能被测试通过。那么能否在测试用例中对表现层进行功能测试呢?答案是可以的,我们可以使用MockMvc来实现它。
67 0
|
安全 Java 测试技术
python接口自动化(三)--如何设计接口测试用例(详解)
上篇我们已经介绍了什么是接口测试和接口测试的意义。在开始接口测试之前,我们来想一下,如何进行接口测试的准备工作。或者说,接口测试的流程是什么?有些人就很好奇,接口测试要流程干嘛?不就是拿着接口文档直接利用接口 测试工具测试嘛。其实,如果只是三五个接口,你可以这么做一个临时的接口测试。但是,如果是上百个接口,或者,你们公司的这个项目,第一次做接口测试,那么,我们还是很有必要严格遵守接口测试的流程。
303 0
python接口自动化(三)--如何设计接口测试用例(详解)
|
测试技术
正交试验测试用例设计及工具推荐
在科研和生产实践中,人们往往要做许多次实验来进行某项研究。实验条件一般包括很多因素,当因素的值不同时,实验的结果也不一样。如果想把每个因素的每个值都要实验一遍,总实验数就等于各因素的值的个数的乘积,而这个数往往很大,超过了可接受的成本。 例如,假设某个实验由A,B,C,D四个因素,每个因素都有10个不同的取值,那么如果想把每个因素都考虑到,我们需要做 10*10*10*10=10000次实验。 为了减少实验数目,我们必须选出那些最有代表性的例子。于是,就要用到了正交表法(Orthogonal Array Testing Strategy)。
268 0
正交试验测试用例设计及工具推荐
|
测试技术 数据库 数据安全/隐私保护
测试用例设计之业务流程分析法
测试用例设计之业务流程分析法
224 0
测试用例设计之业务流程分析法