hardDynamic Programming 1DAI-applied~25 min
Count Valid Decoder State Sequences
A constrained decoder emits one of five state tokens (a, e, i, o, u) per step. The grammar restricts which token may follow which. Count the distinct valid sequences of a given length.
Problem
Count strings of length n over the alphabet {a,e,i,o,u} obeying these follow rules: 'a' may be followed only by 'e'; 'e' only by 'a' or 'i'; 'i' by any vowel except 'i'; 'o' only by 'i' or 'u'; 'u' only by 'a'. Return the count modulo 1e9 + 7.
Input
An integer n (sequence length).
Output
An integer: the number of valid sequences modulo 1e9 + 7.
Constraints
- 1 <= n <= 20000
Examples
Example 1
Input
n = 1
Output
5
Each single token is valid: a, e, i, o, u.
Example 2
Input
n = 2
Output
10
Exactly 10 valid two-token sequences satisfy the follow rules.