学生出勤记录 II

难度: Hard

可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：

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

如果学生能够同时满足下面两个条件，则可以获得出勤奖励：

按 总出勤 计，学生缺勤（'A'）严格少于两天。
学生不会存在连续 3 天或连续 3 天以上的迟到（'L'）记录。

给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况数量。答案可能很大，所以返回对 10⁹ + 7 取余的结果。

示例 1：

输入：n = 2
输出：8
解释：
有 8 种长度为 2 的记录将被视为可奖励：
"PP" , "AP", "PA", "LP", "PL", "AL", "LA", "LL" 
只有"AA"不会被视为可奖励，因为缺勤次数为 2 次（需要少于 2 次）。

示例 2：

输入：n = 1
输出：3

示例 3：

输入：n = 10101
输出：183236316

提示：

1 <= n <= 10⁵

Submission

运行时间: 126 ms

内存: 16.0 MB

class Solution:
    def checkRecord(self, n: int) -> int:
        mod=1000000007
        def mult(mat1,mat2):
            n=len(mat1)
            m=len(mat1[0])
            k=len(mat2[0])
            ans=[[0]*k for _ in range(n)]
            for i in range(n):
                for j in range(k):
                    for l in range(m):
                        ans[i][j]=(ans[i][j]+mat1[i][l]*mat2[l][j])%mod
            return ans

        def f(mat,n,init):
            ans=init
            while n>0:
                if n&1:
                    ans=mult(mat,ans)
                mat=mult(mat,mat)
                n=n>>1
            return ans
        
        init=[[1],[1],[0],[1],[0],[0]]
        base=[[1,1,1,0,0,0],[1,0,0,0,0,0],[0,1,0,0,0,0],
                [1,1,1,1,1,1],[0,0,0,1,0,0],[0,0,0,0,1,0]]
        ans=0
        for i in range(6):
            ans=(ans+f(base,n-1,init)[i][0])%mod
        return ans

Explain

这个题解使用了矩阵快速幂的方法来解决问题。它定义了一个6个状态的转移矩阵，其中每个状态表示当前的出勤记录状态。通过对转移矩阵进行快速幂运算，可以得到从初始状态经过 n-1 次转移后的各个状态的数量。最后将所有状态的数量相加即可得到答案。为了避免大数问题，过程中的计算都对 10^9+7 取模。

时间复杂度: O(logn)

空间复杂度: O(1)

class Solution:
    def checkRecord(self, n: int) -> int:
        mod = 1000000007
        
        # 矩阵乘法
        def mult(mat1, mat2):
            n = len(mat1)
            m = len(mat1[0])
            k = len(mat2[0])
            ans = [[0] * k for _ in range(n)]
            for i in range(n):
                for j in range(k):
                    for l in range(m):
                        ans[i][j] = (ans[i][j] + mat1[i][l] * mat2[l][j]) % mod
            return ans

        # 矩阵快速幂
        def f(mat, n, init):
            ans = init
            while n > 0:
                if n & 1:
                    ans = mult(mat, ans)
                mat = mult(mat, mat)
                n = n >> 1
            return ans
        
        # 初始状态矩阵
        init = [[1], [1], [0], [1], [0], [0]]
        # 状态转移矩阵 
        base = [[1,1,1,0,0,0], [1,0,0,0,0,0], [0,1,0,0,0,0],
                [1,1,1,1,1,1], [0,0,0,1,0,0], [0,0,0,0,1,0]]
        
        ans = 0
        # 计算从初始状态转移 n-1 次后的各状态数量之和 
        for i in range(6):
            ans = (ans + f(base, n-1, init)[i][0]) % mod
        
        return ans

Explore

在题解中，六个状态用于描述学生的出勤记录，具体含义如下：状态0代表没有缺席且结尾没有连续迟到（A=0, L=0），状态1代表没有缺席且结尾有一个迟到（A=0, L=1），状态2代表没有缺席且结尾有两个连续迟到（A=0, L=2），状态3代表有一个缺席且结尾没有连续迟到（A=1, L=0），状态4代表有一个缺席且结尾有一个迟到（A=1, L=1），状态5代表有一个缺席且结尾有两个连续迟到（A=1, L=2）。这六个状态覆盖了学生出勤记录中所有可能的有效组合。

在状态转移矩阵中，每个元素代表从一种状态到另一种状态的转移可能性。例如，base[0][1]的值为1表示状态0（没有缺席且结尾没有连续迟到）可以转移到状态1（没有缺席且结尾有一个迟到），base[3][4]的值为1表示状态3（有一个缺席且结尾没有连续迟到）可以转移到状态4（有一个缺席且结尾有一个迟到）。这些转移表示添加一个新的出勤记录后状态的变化。

矩阵快速幂是一种优化矩阵幂运算的算法，适用于当需要计算矩阵的高次幂时。在这个问题中，将出勤状态的转移表示为一个矩阵，然后通过计算这个矩阵的n-1次幂来得到n天后的状态分布。矩阵快速幂通过分治的思想减少运算次数，当n非常大时，普通的矩阵乘法需要进行n-1次乘法，而矩阵快速幂将复杂度降低到log(n)级别，显著提高了效率。

初始化矩阵 init 表示了第一天可能的出勤状态。在这个问题中，init的设置代表了第一天的六种可能状态：[1], [1], [0], [1], [0], [0]，分别对应状态0至状态5。这里数值1表示该状态在第一天是可能的，数值0表示不可能。例如，第一天有一个连续迟到（状态2）或有一个连续迟到加一个缺席（状态4和状态5）是不可能的。