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

## 封装类

### 核心代码

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

6种状态，故转移矩阵为6行6列，故结果矩阵为6列，6个数据1行就足够了。

mat3[r][c] = Sum[ 0 , k ) i ^{i}_{[0,k)}[0,k)i(mat1[r][i]*mat2[i][c])

i在mat1中列号，在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);
}
}

## 扩展阅读

#### 视频课程

https://edu.csdn.net/course/detail/38771

https://edu.csdn.net/lecturer/6176

#### 测试环境

+17**

|
17天前
|

【消息队列开发】 实现 VirtualHostTests 类——测试虚拟主机操作
【消息队列开发】 实现 VirtualHostTests 类——测试虚拟主机操作
14 0
|
17天前
|

【消息队列开发】 实现MemoryDataCenterTests类——测试管理内存数据
【消息队列开发】 实现MemoryDataCenterTests类——测试管理内存数据
18 3
|
8天前
|
JavaScript Java 测试技术
《手把手教你》系列技巧篇（七十一）-java+ selenium自动化测试-自定义类解决元素同步问题（详解教程）
【6月更文挑战第12天】本文介绍了如何创建一个自定义类库来解决自动化测试中的元素同步问题。作者指出，大部分错误源于元素因时间不同步而引发，为此提供了一种解决方案。在项目实践中，首先在library包下创建名为MyWait的类，包含一个方法isElementPresent，该方法通过循环尝试并等待指定元素出现，避免了直接使用时间等待可能导致的不准确性。之后，在测试类中调用此自定义方法，成功实现了元素同步。代码示例展示了如何在Java+Selenium自动化测试中应用这个自定义类。
28 2
|
14天前
|
Java 测试技术

10 1
|
17天前
|

【消息队列开发】 测试MessageFileManager(对硬盘中的消息操作)类
【消息队列开发】 测试MessageFileManager(对硬盘中的消息操作)类
14 1
|
17天前
|

【消息队列开发】 实现 MqClientTests 类——测试客户端
【消息队列开发】 实现 MqClientTests 类——测试客户端
12 0
|
1月前
|

Spring Boot 自动化单元测试类的编写过程

67 0
|

python接口自动化（三）--如何设计接口测试用例（详解）

303 0
|

268 0
|

224 0