hardDynamic Programming 1DAI-applied~35 min
Count Valid Token Sequences Under Transition Rules
A constrained decoder emits one of five token classes per step, and each class restricts which class may follow it. Count how many distinct length-n sequences obey all transition rules.
Problem
There are five token classes labelled a, e, i, o, u. The successor rules are: a -> e; e -> a or i; i -> any class except i; o -> i or u; u -> a. Given an integer n, return the number of valid length-n strings, modulo 1e9+7.
Input
A single integer n.
Output
An integer: the count of valid sequences modulo 1e9+7.
Constraints
- 1 <= n <= 2*10^4
- Counts are taken modulo 1e9+7.
- Each position holds exactly one of the five classes.
Examples
Example 1
Input
n = 1
Output
5
Any single class is valid.
Example 2
Input
n = 2
Output
10
Ten ordered pairs satisfy the successor rules.