class Solution {
public:
int checkRecord(int n) {
}
};
552. 学生出勤记录 II
可以用字符串表示一个学生的出勤记录，其中的每个字符用来标记当天的出勤情况（缺勤、迟到、到场）。记录中只含下面三种字符：'A'：Absent，缺勤'L'：Late，迟到'P'：Present，到场如果学生能够 同时 满足下面两个条件，则可以获得出勤奖励：
'A'）严格 少于两天。'L'）记录。给你一个整数 n ，表示出勤记录的长度（次数）。请你返回记录长度为 n 时，可能获得出勤奖励的记录情况 数量 。答案可能很大，所以返回对 109 + 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 <= 105相似题目
原站题解
rust 解法, 执行用时: 375 ms, 内存消耗: 27.7 MB, 提交时间: 2024-08-19 09:41:35
impl Solution {
pub fn check_record(n: i32) -> i32 {
fn dfs(i: i32, n: i32, s: &mut Vec<char>, cnt_a: i32, sec_l: i32, mem: &mut Vec<Vec<Vec<i32>>>) -> i32 {
if s.len() as i32 == n { return 1; }
if mem[i as usize][cnt_a as usize][sec_l as usize] > -1 { return mem[i as usize][cnt_a as usize][sec_l as usize]; }
let _mod = 1000000007;
let mut sum = 0;
s.push('P');
sum += dfs(i + 1, n, s, cnt_a, 0, mem);
sum = sum % _mod;
s.pop();
if cnt_a < 1 {
s.push('A');
sum += dfs(i + 1, n, s, cnt_a + 1, 0, mem);
sum = sum % _mod;
s.pop();
}
if sec_l < 2 {
s.push('L');
sum += dfs(i + 1, n, s, cnt_a, sec_l + 1, mem);
sum = sum % _mod;
s.pop();
}
mem[i as usize][cnt_a as usize][sec_l as usize] = sum;
sum
}
dfs(0, n, &mut Vec::new(), 0, 0, &mut vec![vec![vec![-1; 3]; 2]; n as usize])
}
}
python3 解法, 执行用时: 80 ms, 内存消耗: 16 MB, 提交时间: 2023-09-21 10:51:14
class Solution:
# 矩阵快速幂
def checkRecord(self, n: int) -> int:
MOD = 10**9 + 7
mat = [
[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],
]
def multiply(a: List[List[int]], b: List[List[int]]) -> List[List[int]]:
rows, columns, temp = len(a), len(b[0]), len(b)
c = [[0] * columns for _ in range(rows)]
for i in range(rows):
for j in range(columns):
for k in range(temp):
c[i][j] += a[i][k] * b[k][j]
c[i][j] %= MOD
return c
def matrixPow(mat: List[List[int]], n: int) -> List[List[int]]:
ret = [[1, 0, 0, 0, 0, 0]]
while n > 0:
if (n & 1) == 1:
ret = multiply(ret, mat)
n >>= 1
mat = multiply(mat, mat)
return ret
res = matrixPow(mat, n)
ans = sum(res[0])
return ans % MOD
# 三维 dp
def checkRecord1(self, n: int) -> int:
MOD = 10**9 + 7
# 长度，A 的数量，结尾连续 L 的数量
dp = [[[0, 0, 0], [0, 0, 0]] for _ in range(n + 1)]
dp[0][0][0] = 1
for i in range(1, n + 1):
# 以 P 结尾的数量
for j in range(0, 2):
for k in range(0, 3):
dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD
# 以 A 结尾的数量
for k in range(0, 3):
dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD
# 以 L 结尾的数量
for j in range(0, 2):
for k in range(1, 3):
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD
total = 0
for j in range(0, 2):
for k in range(0, 3):
total += dp[n][j][k]
return total % MOD
# 优化dp
def checkRecord2(self, n: int) -> int:
MOD = 10**9 + 7
# A 的数量，结尾连续 L 的数量
dp = [[0, 0, 0], [0, 0, 0]]
dp[0][0] = 1
for i in range(1, n + 1):
dpNew = [[0, 0, 0], [0, 0, 0]]
# 以 P 结尾的数量
for j in range(0, 2):
for k in range(0, 3):
dpNew[j][0] = (dpNew[j][0] + dp[j][k]) % MOD
# 以 A 结尾的数量
for k in range(0, 3):
dpNew[1][0] = (dpNew[1][0] + dp[0][k]) % MOD
# 以 L 结尾的数量
for j in range(0, 2):
for k in range(1, 3):
dpNew[j][k] = (dpNew[j][k] + dp[j][k - 1]) % MOD
dp = dpNew
total = 0
for j in range(0, 2):
for k in range(0, 3):
total += dp[j][k]
return total % MOD
golang 解法, 执行用时: 0 ms, 内存消耗: 1.8 MB, 提交时间: 2023-09-21 10:49:50
func checkRecord1(n int) (ans int) {
const mod int = 1e9 + 7
dp := make([][2][3]int, n+1) // 三个维度分别表示：长度，A 的数量，结尾连续 L 的数量
dp[0][0][0] = 1
for i := 1; i <= n; i++ {
// 以 P 结尾的数量
for j := 0; j <= 1; j++ {
for k := 0; k <= 2; k++ {
dp[i][j][0] = (dp[i][j][0] + dp[i-1][j][k]) % mod
}
}
// 以 A 结尾的数量
for k := 0; k <= 2; k++ {
dp[i][1][0] = (dp[i][1][0] + dp[i-1][0][k]) % mod
}
// 以 L 结尾的数量
for j := 0; j <= 1; j++ {
for k := 1; k <= 2; k++ {
dp[i][j][k] = (dp[i][j][k] + dp[i-1][j][k-1]) % mod
}
}
}
for j := 0; j <= 1; j++ {
for k := 0; k <= 2; k++ {
ans = (ans + dp[n][j][k]) % mod
}
}
return ans
}
// 优化
func checkRecord2(n int) (ans int) {
const mod int = 1e9 + 7
dp := [2][3]int{} // A 的数量，结尾连续 L 的数量
dp[0][0] = 1
for i := 1; i <= n; i++ {
dpNew := [2][3]int{}
// 以 P 结尾的数量
for j := 0; j <= 1; j++ {
for k := 0; k <= 2; k++ {
dpNew[j][0] = (dpNew[j][0] + dp[j][k]) % mod
}
}
// 以 A 结尾的数量
for k := 0; k <= 2; k++ {
dpNew[1][0] = (dpNew[1][0] + dp[0][k]) % mod
}
// 以 L 结尾的数量
for j := 0; j <= 1; j++ {
for k := 1; k <= 2; k++ {
dpNew[j][k] = (dpNew[j][k] + dp[j][k-1]) % mod
}
}
dp = dpNew
}
for j := 0; j <= 1; j++ {
for k := 0; k <= 2; k++ {
ans = (ans + dp[j][k]) % mod
}
}
return ans
}
// 矩阵快速幂
const mod int = 1e9 + 7
type matrix [6][6]int
func (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
}
javascript 解法, 执行用时: 116 ms, 内存消耗: 46.6 MB, 提交时间: 2023-09-21 10:48:33
/**
* @param {number} n
* @return {number}
*/
var checkRecord1 = function(n) {
const MOD = 1000000007;
const dp = new Array(n + 1).fill(2).map(() => new Array(2).fill(0).map(() => new Array(3).fill(0))); // 长度，A 的数量，结尾连续 L 的数量
dp[0][0][0] = 1;
for (let i = 1; i <= n; i++) {
// 以 P 结尾的数量
for (let j = 0; j <= 1; j++) {
for (let k = 0; k <= 2; k++) {
dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD;
}
}
// 以 A 结尾的数量
for (let k = 0; k <= 2; k++) {
dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD;
}
// 以 L 结尾的数量
for (let j = 0; j <= 1; j++) {
for (let k = 1; k <= 2; k++) {
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD;
}
}
}
let sum = 0;
for (let j = 0; j <= 1; j++) {
for (let k = 0; k <= 2; k++) {
sum = (sum + dp[n][j][k]) % MOD;
}
}
return sum;
};
// 优化
var checkRecord2 = function(n) {
const MOD = 1000000007;
let dp = new Array(2).fill(0).map(() => new Array(3).fill(0)); // A 的数量，结尾连续 L 的数量
dp[0][0] = 1;
for (let i = 1; i <= n; i++) {
const dpNew = new Array(2).fill(0).map(() => new Array(3).fill(0));
// 以 P 结尾的数量
for (let j = 0; j <= 1; j++) {
for (let k = 0; k <= 2; k++) {
dpNew[j][0] = (dpNew[j][0] + dp[j][k]) % MOD;
}
}
// 以 A 结尾的数量
for (let k = 0; k <= 2; k++) {
dpNew[1][0] = (dpNew[1][0] + dp[0][k]) % MOD;
}
// 以 L 结尾的数量
for (let j = 0; j <= 1; j++) {
for (let k = 1; k <= 2; k++) {
dpNew[j][k] = (dpNew[j][k] + dp[j][k - 1]) % MOD;
}
}
dp = dpNew;
}
let sum = 0;
for (let j = 0; j <= 1; j++) {
for (let k = 0; k <= 2; k++) {
sum = (sum + dp[j][k]) % MOD;
}
}
return sum;
};
// 矩阵快速幂
var checkRecord = function(n) {
const MOD = BigInt(1000000007);
const pow = (mat, n) => {
let ret = [[1, 0, 0, 0, 0, 0]];
while (n > 0) {
if ((n & 1) === 1) {
ret = multiply(ret, mat);
}
n >>= 1;
mat = multiply(mat, mat);
}
return ret;
}
const multiply = (a, b) => {
const rows = a.length, columns = b[0].length, temp = b.length;
const c = new Array(rows).fill(0).map(() => new Array(columns).fill(BigInt(0)));
for (let i = 0; i < rows; i++) {
for (let j = 0; j < columns; j++) {
for (let k = 0; k < temp; k++) {
c[i][j] += BigInt(BigInt(a[i][k]) * BigInt(b[k][j]));
c[i][j] %= MOD;
}
}
}
return c;
}
const mat = [[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]];
const res = pow(mat, n);
const sum = BigInt(eval(res[0].join("+")));
return sum % MOD;
};
cpp 解法, 执行用时: 4 ms, 内存消耗: 8.3 MB, 提交时间: 2023-09-21 10:47:17
class Solution {
public:
static constexpr int MOD = 1'000'000'007;
int checkRecord1(int n) {
vector<vector<vector<int>>> dp(n + 1, vector<vector<int>>(2, vector<int>(3))); // 长度，A 的数量，结尾连续 L 的数量
dp[0][0][0] = 1;
for (int i = 1; i <= n; i++) {
// 以 P 结尾的数量
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 2; k++) {
dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD;
}
}
// 以 A 结尾的数量
for (int k = 0; k <= 2; k++) {
dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD;
}
// 以 L 结尾的数量
for (int j = 0; j <= 1; j++) {
for (int k = 1; k <= 2; k++) {
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD;
}
}
}
int sum = 0;
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 2; k++) {
sum = (sum + dp[n][j][k]) % MOD;
}
}
return sum;
}
// 优化
int checkRecord2(int n) {
int dp[2][3]; // A 的数量，结尾连续 L 的数量
memset(dp, 0, sizeof(dp));
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
int dpNew[2][3]; // A 的数量，结尾连续 L 的数量
memset(dpNew, 0, sizeof(dpNew));
// 以 P 结尾的数量
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 2; k++) {
dpNew[j][0] = (dpNew[j][0] + dp[j][k]) % MOD;
}
}
// 以 A 结尾的数量
for (int k = 0; k <= 2; k++) {
dpNew[1][0] = (dpNew[1][0] + dp[0][k]) % MOD;
}
// 以 L 结尾的数量
for (int j = 0; j <= 1; j++) {
for (int k = 1; k <= 2; k++) {
dpNew[j][k] = (dpNew[j][k] + dp[j][k - 1]) % MOD;
}
}
memcpy(dp, dpNew, sizeof(dp));
}
int sum = 0;
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 2; k++) {
sum = (sum + dp[j][k]) % MOD;
}
}
return sum;
}
vector<vector<long>> pow(vector<vector<long>> mat, int n) {
vector<vector<long>> ret = {{1, 0, 0, 0, 0, 0}};
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, mat);
}
n >>= 1;
mat = multiply(mat, mat);
}
return ret;
}
vector<vector<long>> multiply(vector<vector<long>> a, vector<vector<long>> b) {
int rows = a.size(), columns = b[0].size(), temp = b.size();
vector<vector<long>> c(rows, vector<long>(columns));
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
for (int k = 0; k < temp; k++) {
c[i][j] += a[i][k] * b[k][j];
c[i][j] %= MOD;
}
}
}
return c;
}
// 矩阵快速幂
int checkRecord(int n) {
vector<vector<long>> mat = {{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}};
vector<vector<long>> res = pow(mat, n);
long sum = accumulate(res[0].begin(), res[0].end(), 0ll);
return (int)(sum % MOD);
}
};
java 解法, 执行用时: 3 ms, 内存消耗: 38.4 MB, 提交时间: 2023-09-21 10:45:23
class Solution {
static final int MOD = 1000000007;
public int checkRecord1(int n) {
// dp[i][j][k] 表示前 i 天有 j 个 ‘A’ 且结尾有连续 k 个 ‘L’ 的可奖励的出勤记录的数量
int[][][] dp = new int[n + 1][2][3]; // 长度，A 的数量，结尾连续 L 的数量
dp[0][0][0] = 1;
for (int i = 1; i <= n; i++) {
// 以 P 结尾的数量
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 2; k++) {
dp[i][j][0] = (dp[i][j][0] + dp[i - 1][j][k]) % MOD;
}
}
// 以 A 结尾的数量
for (int k = 0; k <= 2; k++) {
dp[i][1][0] = (dp[i][1][0] + dp[i - 1][0][k]) % MOD;
}
// 以 L 结尾的数量
for (int j = 0; j <= 1; j++) {
for (int k = 1; k <= 2; k++) {
dp[i][j][k] = (dp[i][j][k] + dp[i - 1][j][k - 1]) % MOD;
}
}
}
int sum = 0;
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 2; k++) {
sum = (sum + dp[n][j][k]) % MOD;
}
}
return sum;
}
// dp[i][][] 只会从dp[i-1][][] 转移，因此可以将 dp 中的总天数的维度省略
public int checkRecord2(int n) {
int[][] dp = new int[2][3]; // A 的数量，结尾连续 L 的数量
dp[0][0] = 1;
for (int i = 1; i <= n; i++) {
int[][] dpNew = new int[2][3];
// 以 P 结尾的数量
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 2; k++) {
dpNew[j][0] = (dpNew[j][0] + dp[j][k]) % MOD;
}
}
// 以 A 结尾的数量
for (int k = 0; k <= 2; k++) {
dpNew[1][0] = (dpNew[1][0] + dp[0][k]) % MOD;
}
// 以 L 结尾的数量
for (int j = 0; j <= 1; j++) {
for (int k = 1; k <= 2; k++) {
dpNew[j][k] = (dpNew[j][k] + dp[j][k - 1]) % MOD;
}
}
dp = dpNew;
}
int sum = 0;
for (int j = 0; j <= 1; j++) {
for (int k = 0; k <= 2; k++) {
sum = (sum + dp[j][k]) % MOD;
}
}
return sum;
}
// 矩阵快速幂
public int checkRecord(int n) {
long[][] mat = {{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}};
long[][] res = pow(mat, n);
long sum = Arrays.stream(res[0]).sum();
return (int) (sum % MOD);
}
public long[][] pow(long[][] mat, int n) {
long[][] ret = {{1, 0, 0, 0, 0, 0}};
while (n > 0) {
if ((n & 1) == 1) {
ret = multiply(ret, mat);
}
n >>= 1;
mat = multiply(mat, mat);
}
return ret;
}
public long[][] multiply(long[][] a, long[][] b) {
int rows = a.length, columns = b[0].length, temp = b.length;
long[][] c = new long[rows][columns];
for (int i = 0; i < rows; i++) {
for (int j = 0; j < columns; j++) {
for (int k = 0; k < temp; k++) {
c[i][j] += a[i][k] * b[k][j];
c[i][j] %= MOD;
}
}
}
return c;
}
}