The clean round bonus

A dairy depot pays a bonus on a clean round, and the rules are loose enough that most logs still qualify. The question is how many.

The problem

Every morning a courier's round is written into the depot log as one letter: D if the crates went out on time, L if they went out late, M if the round was missed.

At the end of a stretch of days mornings the depot pays a bonus, unless either rule is broken. The log may hold at most one M in the whole stretch, and it may never hold three L mornings in a row.

Count how many different logs of exactly days letters earn the bonus. The count grows quickly, so report it modulo 1,000,000,007.

Input. days — the length of the stretch.

Output. The number of bonus-earning logs of that length, modulo 10^9 + 7.

Example.

days = 2   ->  8

There are nine two-letter logs. Only MM fails, by spending a second miss.

A second example, where both rules bite:

days = 3   ->  19

Of the 27 three-letter logs, seven hold two or more M mornings and one is LLL, leaving 19.

Constraints.

• 1 <= days <= 10^5
• The answer is taken modulo 10^9 + 7

Hints

Approach

Brute force

Write out all 3^days logs and test each against both rules. At days = 20 that is already 3.5 billion logs, and the stretch can run to 100,000 mornings.

The insight

A log's future depends on two facts alone — whether the single permitted miss is spent, and the length of the run of late mornings at the end — so every log sharing those two facts can be held as one number rather than listed.

Neither rule looks deeper. "At most one M" is a running total that stops at 1, and "no three L in a row" only ever reads the last two letters. Six states cover every log, and one morning maps each state to at most three others, always the same way, so the six counts after day i determine the six counts after day i + 1 without reference to anything earlier.

Algorithm

1. Hold ways[m][r]: logs with m misses spent and a run of r late mornings at the end. Seed ways[0][0] = 1 — the empty log — and zero the rest.
2. For each morning build a fresh table and move every count:
   • D sends (m, r) to (m, 0) — the run resets.
   • L sends (m, r) to (m, r + 1), only while r < 2.
   • M sends (0, r) to (1, 0) — only from a log with no miss yet, and it ends the run as well.
3. Reduce every addition modulo 10^9 + 7.
4. After days mornings, the answer is the sum of all six counts.

Complexity

Time O(days) — six states, three moves each, so 18 additions a morning and about 1.8 million for the longest stretch. Space O(1) — two tables of six numbers, whatever the length of the round.

Solution

"""The clean round bonus — counting DP over (missed mornings, trailing late run)."""

MOD = 10**9 + 7


def solve(days):
    # ways[m][r]: records written so far that have m missed mornings and end on a
    # run of r late ones. Every legal record sits in exactly one bucket, so the
    # six numbers are a complete summary of the past.
    ways = [[0, 0, 0], [0, 0, 0]]
    ways[0][0] = 1                       # the empty record, before day one
    for _ in range(days):
        nxt = [[0, 0, 0], [0, 0, 0]]
        for missed in (0, 1):
            for run in (0, 1, 2):
                count = ways[missed][run]
                if not count:
                    continue
                nxt[missed][0] = (nxt[missed][0] + count) % MOD
                if run < 2:              # a third late morning in a row is barred
                    nxt[missed][run + 1] = (nxt[missed][run + 1] + count) % MOD
                if missed == 0:          # the single miss the bonus allows
                    nxt[1][0] = (nxt[1][0] + count) % MOD
        ways = nxt
    return sum(sum(row) for row in ways) % MOD

TESTS = [
    ((1,), 3),
    ((2,), 8),
    ((3,), 19),
    ((4,), 43),
    ((5,), 94),
    ((10,), 3536),
    ((100000,), 749184020),
]

Pitfalls

• Forgetting the guard on the third L. Without r < 2 the third late morning is allowed and days = 3 returns 20 rather than 19.
• Letting M keep the late run. A missed morning is not a late one, so it has to land on (1, 0). Carrying the run forward blocks logs like L L M L, and days = 4 comes back 41 instead of 43.
• Writing the new counts into the table being read. A count already moved this morning gets moved again, so one morning is applied twice; days = 2 returns 210 instead of 8. Build a fresh table each morning.

Variants

• Setting the folios — another counting scan whose state is a couple of flags, over positions rather than mornings.
• Counterweight rig — the same single-pass table, holding reachability instead of counts.