矩阵快速幂优化状态机dp，LeetCode 552. 学生出勤记录 II
一、题目
1、题目描述
可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：
'A'：Absent，缺勤'L'：Late，迟到'P'：Present，到场如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
- 按 总出勤 计，学生缺勤（
'A'）严格 少于两天。- 学生 不会 存在 连续 3 天或 连续 3 天以上的迟到（
'L'）记录。给你一个整数
n，表示出勤记录的长度（次数）。请你返回记录长度为n时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对109 + 7取余 的结果。
2、接口描述
cpp
class Solution {
public:int checkRecord(int n) {}
};
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的情况数，转移如下：
f(i + 1, 0) = f(i, 0) + f(i, 1) + f(i, 2)
f(i + 1, 1) = f(i, 0)
f(i + 1, 2) = f(i, 1)
f(i + 1, 3) = f(i, 0) + f(i, 1) + f(i, 2)
f(i + 1, 4) = f(i, 3) + f(i, 4) + f(i, 5) + f(i, 6)
f(i + 1, 5) = f(i, 3) + f(i, 4)
f(i + 1, 6) = f(i, 5)我们可以O(N)进行计算，也可以矩阵快速幂优化状态机dp
2、复杂度
时间复杂度： O(log(n) * 7^3)空间复杂度：O(7^3)
3、代码详解
cpp
using i64 = long long;
constexpr int P = 1E9 + 7;struct Matrix {int m, n;std::vector<std::vector<int>> g;Matrix(int _m, int _n) : m(_m), n(_n), g(_m, std::vector<int>(_n)){}Matrix(const std::vector<std::vector<int>> &_init) : m(_init.size()), n(_init[0].size()), g(_init) {}Matrix(const Matrix &a) : Matrix(a.g) {}void init() {assert(m == n); for (int i = 0; i < m; ++ i)g[i].assign(m, 0), g[i][i] = 1;}const std::vector<int>& operator [] (int i) const {assert(i < m);return g[i];}void show() const {for (int i = 0; i < m; ++ i)for (int j = 0; j < n; ++ j) std::cout << g[i][j] << " \n"[j + 1 == n]; std::cout << '\n';}friend inline Matrix operator * (const Matrix &a, const Matrix &b) {int m = a.m, n = b.n, t = a.n;Matrix res(m, n);for (int i = 0; i < m; ++ i)for (int k = 0; k < t; ++ k)for (int j = 0; j < n; ++ j) res.g[i][j] = (res.g[i][j] + 1LL * a[i][k] * b[k][j] % P) % P;return res;}friend inline Matrix power(Matrix a, i64 b) {Matrix res(a.m, a.m);res.init(); for (; b; b >>= 1, a = a * a) if (b & 1)res = res * a;return res;}
};class Solution {
public:int checkRecord(int n) {std::vector<std::vector<int>> a(1, {1, 0, 0, 0, 0, 0, 0}), b({{1, 1, 0, 1, 0, 0, 0},{1, 0, 1, 1, 0, 0, 0},{1, 0, 0, 1, 0, 0, 0},{0, 0, 0, 0, 1, 1, 0},{0, 0, 0, 0, 1, 1, 0},{0, 0, 0, 0, 1, 0, 1},{0, 0, 0, 0, 1, 0, 0}});Matrix base(a), help(b);auto g = (base * power(help, n)).g[0];return std::accumulate(g.begin(), g.end(), 0LL) % P;}
};