▶ 一个学生的考勤状况是一个字符串，其中各字符的含义是：A 缺勤，L 迟到，P 正常。如果一个学生考勤状况中 A 不超过一个，且没有连续两个 L（L 可以有多个，但是不能连续），则称该学生达标（原文表述：A student could be rewarded if his attendance record doesn't contain more than one 'A' (absent) or more than two continuous 'L' (late). ）
▶ 551. 给定一个学生的考勤状况，判断他能否达标。
● 代码，4 ms，简单的计数，最快的解法算法与之相同
class Solution
{
public:
bool checkRecord(string s)
{
int i, a, l;
for (i = a = l = ; i < s.size(); i++)
{
if (s[i] == 'A')
a++;
if (s[i] == 'L')
l++;
else // 出现 A 或 P 时均要清空 L 计数
l = ;
if (a >= || l > )
return false;
}
return true;
}
};
▶ 552. 给定正整数 n，考虑所有长度为 n 的考勤状况（3n 种可能），计算达标的考勤状况数，该数字可能非常大，取关于 109 + 7（竟然是个素数）模作为输出结果
● 自己的代码，29 ms，时间复杂度 O(n)，考虑递推数列，一个达标序列只能是以下三种情况：
a[ k ] 表长度为 k，以 P 结尾，不含 A 的达标序列个数
b[ k ] 表长度为 k，以 PL 结尾，不含 A 的达标序列个数（不能是 LLLP 结尾）
c[ k ] 表长度为 k，以 LL 结尾，不含 A 的达标序列个数（不能是 LLL 结尾）
注意到 a[ 1 ] = b[ 1 ] = 1，c[ 1 ] = 0，a[ k ] = a[ k - 1 ] + b[ k - 1 ] + c[ k - 1]（任意一种达标序列添个 P），b[ k ] = a[ k - 1 ]（P 结尾的达标序列添个 L），c[ k ] = b[ k - 1 ]（PL 结尾的达标序列添个 L）
约化后就变成了 a[ 1 ] = 1，a[ 2 ] = 2，a[ 3 ] = 4，a[ n ] = a[ n - 1 ] + a[ n - 2 ] + a[ n - 3 ] ( n ≥ 4 )
对上述数列打表，使用长度为 n+1 的表 f，其中 a[ k ] = f[ k - 1 ]，即所有下标有一单位的平移，在代码中注意控制
因为打表序列中 A 至多一个，所以按照 A 的位置分类讨论：
① 不含A，一共有 a[ n ] + b[ n ] + c[ n ] = a[ n + 1 ] 种情况，等于 f[ n ]（打表要长一格的原因）
② A 在开头，一共有 a[ n - 1 ] + b[ n - 1 ] + c[ n - 1 ] = a[ n ] 种情况，等于 f[ n - 1 ]
③ A 在结尾，同上，等于 f[ n - 1 ]
④ A 在中间，考虑 A 的左边有长度为 i 的不含 A 的序列，且 A 的右边有长度为 n - i - 1 的不含A的序列，一共是 ( a[ i ] + b[ i ] + c[ i ] ) * ( a[ n - i - 1 ] + b[ n - i - 1 ] + c[ n - i - 1 ] )，即 f[ i ] * f[ n - i - 1 ]，
i 在 i = 1 到 i = n - 2 之间求和。
注意每一步取模运算，因为 f 本身是指数级增长的。
class Solution
{
public:
int checkRecord(int n)
{
if (n == )
return ;
const int m = ;
vector<long long> f(n + , );
int i,sum;
for (f[] = , f[] = , f[] = , i = ; i <= n; f[i] = (f[i - ] + f[i - ] + f[i - ]) % m, i++);
for (sum = (f[n] + f[n - ] * ) % m, i = ; i < n - ; i++)
sum = (sum + f[i] * f[n - i - ]) % m;
return sum;
}
};
● 代码，4 ms，使用一个矩阵的幂来计算递推
#define ENTRY(A, i, j) ((A)[(i) * n + (j)]) int64_t* NewMatrix(size_t n)
{
assert(n >= );
int64_t* temp = (int64_t*)calloc(n * n, sizeof(int64_t));
assert(temp != NULL);
return temp;
} void FreeMatrix(int64_t* A)
{
free(A);
} void SetMatrix(int64_t* A, int64_t* B, size_t n)
{
memcpy(A, B, n * n * sizeof(int64_t));
} void IdentityMatrix(int64_t* A, size_t n)// 将方阵 A 赋值为单位方阵
{
int i, j;
for (i = ; i < n; i++)
{
for (j = ; j < n; j++)
ENTRY(A, i, j) = (i == j);
}
} void MatrixMultiply(int64_t* A, int64_t* B, size_t n)// 方阵乘法 A = A * B
{
assert(n >= );
int64_t* C = NewMatrix(n);
int i, j, k;
for (i = ; i < n; ++i)
{
for (j = ; j < n; ++j)
{
ENTRY(C, i, j) = ;
for (k = ; k < n; ++k)
ENTRY(C, i, j) += ENTRY(A, i, k) * ENTRY(B, k, j);
}
}
memcpy(A, C, n * n * sizeof(int64_t));
FreeMatrix(C);
} void MatrixPower(int64_t* C, int64_t* A, size_t n, int m)// 方阵幂 C = A ^ m
{
assert(n >= );
assert(m >= );
int64_t* B = NewMatrix(n);
SetMatrix(B, A, n);
IdentityMatrix(C, n);
for (; m > ; m /= )// 二进制方法
{
if (m % == )
MatrixMultiply(C, B, n);
MatrixMultiply(B, B, n);
}
FreeMatrix(B);
} void MatrixModulus(int64_t* A, size_t n, int64_t modulus)// 方阵逐格求模 A %= m
{
int i, j;
for (i = ; i < n; ++i)
{
for (j = ; j < n; ++j)
ENTRY(A, i, j) = ENTRY(A, i, j) % modulus;
}
} void MatrixModulusPower(int64_t* C, int64_t* A, size_t n, int m, int64_t modulus)// C = A ^ m % modulus
{
assert(n >= );
assert(m >= );
int64_t* B = NewMatrix(n);
SetMatrix(B, A, n);
IdentityMatrix(C, n);
for (; m > ;m/=)
{
if (m % == )
{
MatrixMultiply(C, B, n);
MatrixModulus(C, n, modulus);
}
MatrixMultiply(B, B, n);
MatrixModulus(B, n, modulus);
}
FreeMatrix(B);
} int AttendanceNumber(int m)
{
assert(m >= );
size_t n = ;
int64_t initial_vector[] = { , , , , , };
int64_t modulus = ;
int64_t* A = NewMatrix(n);
ENTRY(A, , ) = ;
ENTRY(A, , ) = ;
ENTRY(A, , ) = ;
ENTRY(A, , ) = ;
ENTRY(A, , ) = ;
ENTRY(A, , ) = -;
ENTRY(A, , ) = -;
ENTRY(A, , ) = -;
ENTRY(A, , ) = ;
ENTRY(A, , ) = ;
ENTRY(A, , ) = ;
int64_t answer = ;
if (m <= )
answer = initial_vector[m];
else
{
int64_t* C = NewMatrix(n);
MatrixModulusPower(C, A, n, m - n + , modulus);
for (size_t i = ; i < n; ++i)
answer += ENTRY(C, n - , i) * initial_vector[i];
answer = (answer % modulus + modulus) % modulus;
FreeMatrix(C);
}
FreeMatrix(A);
return answer;
} #undef ENTRY class Solution
{
public:
int checkRecord(int n)
{
return AttendanceNumber(n);
}
};
● 初版动态规划（MLE），f[ i ][ j ][ k ] 表示长度为 i，至多 j 个 A，至多 k 个连续 L 的序列。所求目标为 f[ n ][ 1 ][ 2 ]，转移方程如下，发现可以用矩阵幂来一次性计算 f[ n ]
class Solution
{
public:
int checkRecord(int n)
{
const int MOD = ;
vector<vector<vector<int>>> f(n + , vector<vector<int>>(, vector<int>(3, 0)));
int i, j, k, val;
for (i = ; i < ; i++)
for (j = ; j < ; f[][i][j++] = );
for (i = ; i <= n; i++)
{
for (j = ; j < ; j++)
{
for (k = ; k < ; k++)
{
val = f[i - ][j][]; // P
if (j > ) // A
val = (val + f[i - ][j - ][]) % MOD;
if (k > ) // L
val = (val + f[i - ][j][k - ]) % MOD;
f[i][j][k] = val;
}
}
}
return f[n][][];
}
};
● 改进动态规划，8 ms，直接用矩阵幂来计算
class Solution
{
public:
const int MOD = , M = ;
void mul(vector<vector<int>>& A, vector<vector<int>>& B)
{
vector<vector<int>> temp(M, vector<int>(M, ));
int i, j, k;
for (i = ; i < M; i++)
{
for (j = ; j < M; j++)
{
for (k = ; k < M; k++)
temp[i][j] = (int)((temp[i][j] + (long)A[i][k] * B[k][j]) % MOD);
}
}
A = temp;
return;
}
void pow(vector<vector<int>>& A, int n)
{
vector<vector<int>> temp(M, vector<int>(M, ));
for (int i = ; i < M; temp[i][i] = , i++);
for (; n > ; n /= )
{
if (n % )
mul(temp, A);
mul(A, A);
}
A = temp;
return;
}
int checkRecord(int n)
{
vector<vector<int>> A = \
{
{ , , , , , },
{ , , , , , },
{ , , , , , },
{ , , , , , },
{ , , , , , },
{ , , , , , },
};
pow(A, n + );
return A[][];
}
};
● 代码，深度优先遍历，TLE，说明穷举肯定不行
class Solution
{
public:
int checkRecord(int n)
{
long long res = ;
dfs(n, , , , res);
return res % ;
}
void dfs(int n, int s, int A, int L, long long& res)// 当前共 s 位，有 A 个 A 和 L 个 L
{
if (s == n)
{
res++;
return;
}
dfs(n, s + , A, , res); //add "P"
if (A < )
dfs(n, s + , A + , , res);
if (L <= )
dfs(n, s + , A, L + , res);
}
};