Shuffle
Time limit2sMemory limit128 MB
Count song sequences (repeatable, with genre transition rules and per-song lengths 1 to 9) whose total play time lies in [A, B], modulo a prime.
- Level
Hard8 of 10
- Topics
- Dynamic programming, Matrix, Graph, Combinatorics
- Solved
- No attempts yet
Problem
A music player plays songs in a shuffled order. There are several genres, and each song belongs to exactly one genre. For every pair of genres, it is known whether a song of the second genre may be played immediately after a song of the first genre. If genre j is allowed after genre i, then after listening to a song of genre i, the next song may have genre j.
The first song may be any song. After that, the next song must belong to a genre that is allowed after the genre of the previous song. The same song may be played multiple times, and it may also be played twice in a row.
Count the number of playable song sequences whose total playing time is at least A and at most B.
Input
The first line contains the number of songs N. N is between 1 and 1000, inclusive.
Each of the next N lines contains the genre number and length of one song. Genre numbers range from 0 to M-1, and every song length is between 1 and 9, inclusive.
The next line contains the number of genres M. M is between 1 and 9, inclusive.
The next M lines describe the genre compatibility relation as an adjacency matrix. If the jth character of the ith row is Y, a song of genre j may be played after a song of genre i; if it is N, it may not. Let this matrix be T; for every i, T[i][i] = Y.
The last line contains A and B. B is at least A, and both A and B are between 1 and 1,000,000,000, inclusive.
Output
Print the number of song sequences whose total playing time is at least A and at most B, modulo 600921647.