Golang | Leetcode Golang题解之第552题学生出勤记录II

题目：

题解：

const mod int = 1e9 + 7type matrix [6][6]intfunc (a matrix) mul(b matrix) matrix {c := matrix{}for i, row := range a {for j := range b[0] {for k, v := range row {c[i][j] = (c[i][j] + v*b[k][j]) % mod}}}return c
}func (a matrix) pow(n int) matrix {res := matrix{}for i := range res {res[i][i] = 1}for ; n > 0; n >>= 1 {if n&1 > 0 {res = res.mul(a)}a = a.mul(a)}return res
}func checkRecord(n int) (ans int) {m := matrix{{1, 1, 0, 1, 0, 0},{1, 0, 1, 1, 0, 0},{1, 0, 0, 1, 0, 0},{0, 0, 0, 1, 1, 0},{0, 0, 0, 1, 0, 1},{0, 0, 0, 1, 0, 0},}res := m.pow(n)for _, v := range res[0] {ans = (ans + v) % mod}return ans
}