552. 学生出勤记录 II
给定一个正整数 n，返回长度为 n 的所有可被视为可奖励的出勤记录的数量。 答案可能非常大，你只需返回结果mod 109 + 7的值。
学生出勤记录是只包含以下三个字符的字符串：
‘A’ : Absent，缺勤
‘L’ : Late，迟到
‘P’ : Present，到场
如果记录不包含多于一个’A’（缺勤）或超过两个连续的’L’（迟到），则该记录被视为可奖励的。
示例 1:
输入: n = 2
输出: 8
解释：
有8个长度为2的记录将被视为可奖励：
“PP” , “AP”, “PA”, “LP”, “PL”, “AL”, “LA”, “LL”
只有"AA"不会被视为可奖励，因为缺勤次数超过一次。
注意：n 的值不会超过100000。
先附上大佬用数学方法做的：
用数组放入关系，太顶了
下面才是我写的勉强过关的代码
class Solution {
public int checkRecord(int n) {
long[][] a = new long[][]{{1},{1},{0},{1},{0},{0}};
long[][] aMatrix = new long[][]{{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}};
while (n>0) {
int m = n & 1;
if (m == 1) {
a = this.multipleMatrix(aMatrix, a);
}
aMatrix = this.multipleMatrix(aMatrix, aMatrix);
n = n>>1;
}
/**
* 0 A0L0
* 1 A0L1
* 2 A0L2
* 3 A1L0
* 4 A1L1
* 5 A1L2
*/
return (int)a[3][0];
}
public long[][] multipleMatrix(long[][] a,long[][] b) {
long mod = (long)1e9+7;
long c[][] = new long[a.length][b[0].length];
for (int i = 0; i < a.length; i++) {
for (int j = 0; j < b[i].length; j++) {
for (int k = 0; k < a[i].length; k++) {
c[i][j] = (c[i][j] + a[i][k] * b[k][j]) % mod;
}
}
}
return c;
}
}
class Solution {
long M = 1000000007;
public int checkRecord(int n) {
long[] f = new long[n <= 5 ? 6 : n + 1];
f[0] = 1;
f[1] = 2;
f[2] = 4;
f[3] = 7;
//四种情况下，我前三个可奖励，我最后一个是l是p无所谓
//如果中间出现两个LL，那么我必定无效
//2*f[i-1]和一个-f[i-4]
for (int i = 4; i <= n; i++)
f[i] = ((2 * f[i - 1]) % M + (M - f[i - 4])) % M;
long sum = f[n];
for (int i = 1; i <= n; i++) {
sum += (f[i - 1] * f[n - i]) % M;
}
return (int)(sum % M);
}
}