0552. Student Attendance Record II¶
题目信息¶
- 题号:
0552
- 难度:
Hard
- 主题:
出勤记录计数、长度固定、缺席上限、连续迟到、取模
- 原题:
- 重点:
统计所有长度为 n 的合法字符串、A 最多一个、不能含 LLL、答案对 10^9+7 取模
题目重述¶
给定正整数 n,统计长度恰好为 n 的出勤记录字符串数量。每个位置可以是 'A'、'L' 或 'P',但合法记录必须同时满足:整个字符串中至多出现一次 A;任何位置都不能出现连续三个 L。
返回合法记录数量对 1,000,000,007 取模后的结果。不同字符串按字符序列区分;这是统计所有可能记录,而不是判断某一条已给定记录。
自建示例¶
长度为一:
输入:n = 1
输出:3
解释:"A"、"L"、"P" 三种记录都合法。
长度为二:
输入:n = 2
输出:8
解释:共有 9 个字符串,只有 "AA" 因出现两次缺席而不合法;长度 2 不可能含有 LLL。
状态记录缺席数和连续迟到数¶
构造记录时,合法性的未来只取决于已经使用了几次 A``(0 或 1)以及末尾连续 ``L 的长度(0、1 或 2)。在每个状态后追加 P、A 或 L,若不违反限制就把方案数转移到新状态,并按模数保存。
C++ 实现¶
class Solution {
public:
int checkRecord(int n) {
const int mod = 1000000007;
std::array<std::array<long long, 3>, 2> dp{};
dp[0][0] = 1;
for (int day = 0; day < n; ++day) {
std::array<std::array<long long, 3>, 2> next{};
for (int absent = 0; absent <= 1; ++absent) {
for (int late = 0; late <= 2; ++late) {
long long ways = dp[absent][late];
if (ways == 0) continue;
next[absent][0] =
(next[absent][0] + ways) % mod; // P
if (absent == 0) {
next[1][0] = (next[1][0] + ways) % mod; // A
}
if (late < 2) {
next[absent][late + 1] =
(next[absent][late + 1] + ways) % mod;
}
}
}
dp = next;
}
long long answer = 0;
for (const auto& row : dp) {
for (long long ways : row) answer = (answer + ways) % mod;
}
return static_cast<int>(answer);
}
};
代码分析¶
状态中的两个维度正好保存追加字符所需的历史信息,所有合法记录都沿唯一字符序列转移到某个终态,非法的第二个 A 或第三个连续 L 不进入状态。状态数固定为 6,每天处理常数转移,时间复杂度为 O(n),空间复杂度为 O(1)。