矩阵快速幂优化状态机dp，LeetCode 552. 弟子出勤记载 II

一、标题

1、标题形貌

   可以用字符串体现一个弟子的出勤记载，此中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记载中只含下面三种字符：
  

• 'A'：Absent，缺勤
  
• 'L'：Late，迟到
  
• 'P'：Present，到场
  

如果弟子可以大概 同时 满足下面两个条件，则可以得到出勤嘉奖：
  

• 按 总出勤 计，弟子缺勤（'A'）严酷 少于两天。
  
• 弟子 不会 存在 连续 3 天或 连续 3 天以上的迟到（'L'）记载。
  

给你一个整数 n ，体现出勤记载的长度（次数）。请你返回记载长度为 n 时，大概得到出勤嘉奖的记载情况 数目 。答案大概很大，以是返回对 109 + 7 取余 的结果。
  2、接口形貌

cpp

1. class Solution {
2. public:
3.     int checkRecord(int n) {
5.     }
6. };

复制代码

1.  ​

复制代码

3、原题链接

552. Student Attendance Record II

---

二、解题陈诉

1、思绪分析

矩阵快速幂见：矩阵快速幂及应用实战[C/C++]_c++矩阵快速幂-CSDN博客
思量状态机：
7 种
0 0A 0L，空大概以P末端
1 0A, 1L，以L末端
2 0A，2L，以2L末端
3 1A，0L，以A末端
4 1A，0L，以P末端
5 1A，1L，以L末端
6 1A，2L，以2L末端
那么我们界说f(i, j) 为前i个字符，状态为j的情况数，转移如下：

1. f(i + 1, 0) = f(i, 0) + f(i, 1) + f(i, 2)
2. f(i + 1, 1) = f(i, 0)
3. f(i + 1, 2) = f(i, 1)
4. f(i + 1, 3) = f(i, 0) + f(i, 1) + f(i, 2)
5. f(i + 1, 4) = f(i, 3) + f(i, 4) + f(i, 5) + f(i, 6)
6. f(i + 1, 5) = f(i, 3) + f(i, 4)
7. f(i + 1, 6) = f(i, 5)

复制代码

我们可以O(N)举行盘算，也可以矩阵快速幂优化状态机dp
2、复杂度

   时间复杂度： O(log(n) * 7^3)空间复杂度：O(7^3)
  
3、代码详解

cpp

1. using i64 = long long;
2. constexpr int P = 1E9 + 7;
4. struct Matrix {
5.     int m, n;
6.     std::vector<std::vector<int>> g;
7.    
8.     Matrix(int _m, int _n) : m(_m), n(_n), g(_m, std::vector<int>(_n)){}
9.     Matrix(const std::vector<std::vector<int>> &_init) : m(_init.size()), n(_init[0].size()), g(_init) {}
10.     Matrix(const Matrix &a) : Matrix(a.g) {}
12.     void init() {
13.         assert(m == n);
14.         for (int i = 0; i < m; ++ i)
15.             g[i].assign(m, 0), g[i][i] = 1;
16.     }
18.     const std::vector<int>& operator [] (int i) const {
19.         assert(i < m);
20.         return g[i];
21.     }
23.     void show() const {
24.         for (int i = 0; i < m; ++ i)
25.             for (int j = 0; j < n; ++ j)
26.                 std::cout << g[i][j] << " \n"[j + 1 == n]; std::cout << '\n';
27.     }
29.     friend inline Matrix operator * (const Matrix &a, const Matrix &b) {
30.         int m = a.m, n = b.n, t = a.n;
31.         Matrix res(m, n);
32.         for (int i = 0; i < m; ++ i)
33.             for (int k = 0; k < t; ++ k)
34.                 for (int j = 0; j < n; ++ j)
35.                     res.g[i][j] = (res.g[i][j] + 1LL * a[i][k] * b[k][j] % P) % P;
36.         return res;
37.     }
39.     friend inline Matrix power(Matrix a, i64 b) {
40.         Matrix res(a.m, a.m);
41.         res.init();
42.         for (; b; b >>= 1, a = a * a)
43.             if (b & 1)
44.                 res = res * a;
45.         return res;
46.     }
47. };
49. class Solution {
50. public:
51.     int checkRecord(int n) {
52.         std::vector<std::vector<int>> a(1, {1, 0, 0, 0, 0, 0, 0}),
53.         b({
54.             {1, 1, 0, 1, 0, 0, 0},
55.             {1, 0, 1, 1, 0, 0, 0},
56.             {1, 0, 0, 1, 0, 0, 0},
57.             {0, 0, 0, 0, 1, 1, 0},
58.             {0, 0, 0, 0, 1, 1, 0},
59.             {0, 0, 0, 0, 1, 0, 1},
60.             {0, 0, 0, 0, 1, 0, 0}
61.         });
62.         Matrix base(a), help(b);
63.         auto g = (base * power(help, n)).g[0];
64.         return std::accumulate(g.begin(), g.end(), 0LL) % P;
65.     }
66. };

复制代码

1.  ​

复制代码