hardDynamic Programming 2DAI-applied~45 min
Count Generations With Per-Symbol Repeat Caps
A sampler draws n symbols from a 6-way categorical distribution, but each symbol class may not repeat more than a per-class limit consecutively. Count how many distinct length-n generations satisfy all caps.
Problem
A die has faces 1..6. Given n rolls and an array rollMax where rollMax[i] is the maximum number of times face i+1 may appear consecutively, return the number of distinct roll sequences of length n, modulo 1e9+7.
Input
An integer n and an array rollMax of length 6.
Output
An integer: the count of valid sequences modulo 1e9+7.
Constraints
- 1 <= n <= 5000
- 1 <= rollMax[i] <= 15
- There are exactly 6 faces.
Examples
Example 1
Input
n = 2, rollMax = [1,1,2,2,2,3]
Output
34
Of 36 sequences, the two with a repeated face 1 or face 2 are excluded.
Example 2
Input
n = 3, rollMax = [1,1,1,2,2,3]
Output
181
Counting all length-3 sequences honoring the caps gives 181.