Encode both rules into one state machine: how many A’s used (0/1) × trailing consecutive L’s (0/1/2) → 6 states.Solution 1: DP — O(n) time, O(1) space (recommended)class Solution {private static final long MOD 1_000_000_007L;public int checkRecord(int n) { long[][] dp new long[2][3]; dp[0][0] 1; // empty prefix for (int i 0; i n; i) { long[][] next new long[2][3]; for (int a 0; a 2; a) { for (int l 0; l 3; l) { long v dp[a][l]; if (v 0) continue; next[a][0] (next[a][0] v) % MOD; // append P if (a 0) next[1][0] (next[1][0] v) % MOD; // append A if (l 2) next[a][l 1] (next[a][l 1] v) % MOD; // append L } } dp next; } long ans 0; for (int a 0; a 2; a) for (int l 0; l 3; l) ans (ans dp[a][l]) % MOD; return (int) ans; }}Solution 2: Matrix exponentiation — O(log n)Flatten the states with“idx a * 3 l”, fill a 6×6 matrix using the same three transitions, binary-exponentiate it, then sum column 0 (the initial vector is“e[(0,0)]”). Full code is in the file.Common pitfallsUse“long” for intermediates —“int” overflows on the product of two ~1e9 values.“No“LLL”” means trailing L’s may reach at most 2; prune the transition that would make it 3.“n 0” returns 1 (the empty record counts).Both versions were cross-checked against brute-force enumeration for n 0…8, and they agree at“n 10101” →“183236316”.
