hardDynamic Programming 1DAI-applied~35 min
Count Acceptable Daily-Status Logs of Length N
Each day a training job logs Present, Late, or Aborted. A log is acceptable only if it records fewer than 2 Aborted days total and never 3 or more consecutive Late days. Count acceptable length-n logs.
Problem
Each record is one of 'P', 'L', or 'A'. A length-n record string is rewardable if it contains fewer than 2 'A' in total and does not contain 3 or more consecutive 'L'. Given n, return the number of rewardable strings, modulo 1e9+7.
Input
A single integer n.
Output
An integer: the count of valid records modulo 1e9+7.
Constraints
- 1 <= n <= 10^5
- Counts are taken modulo 1e9+7.
- Each day is one of P, L, A.
Examples
Example 1
Input
n = 2
Output
8
Of 9 length-2 strings, only 'AA' is invalid, leaving 8.
Example 2
Input
n = 1
Output
3
P, L, and A are all valid.