VocaloidsAndSongs
SRM 609 · 2013-12-22 · by semiexp
SRM 609 · 2013-12-22 · by semiexp · Dynamic Programming, Simple Math
Problem Statement
Problem Statement
Vocaloids Gumi, Ia, and Mayu love singing.
They decided to make an album composed of S songs.
Each of the S songs must be sung by at least one of the three Vocaloids.
It is allowed for some songs to be sung by any two, or even all three Vocaloids at the same time.
The number of songs sang by Gumi, Ia, and Mayu must be gumi, ia, and mayu, respectively.
They soon realized that there are many ways of making the album. Two albums are considered different if there is a song that is sung by a different set of Vocaloids. Let X be the number of possible albums. Since the number X can be quite large, compute and return the number (X modulo 1,000,000,007).
They soon realized that there are many ways of making the album. Two albums are considered different if there is a song that is sung by a different set of Vocaloids. Let X be the number of possible albums. Since the number X can be quite large, compute and return the number (X modulo 1,000,000,007).
Constraints
- S will be between 1 and 50, inclusive.
- gumi, ia and mayu will be each between 1 and S, inclusive.
Examples
0)
3 1 1 1 Returns: 6
In this case, there are 3 songs on the album. And Gumi, Ia, Mayu will each sing one song. There are 3*2*1 = 6 ways how to choose which Vocaloid sings which song.
1)
3 3 1 1 Returns: 9
Gumi will sing all three songs. Ia and Mayu can each choose which one song they want to sing.
2)
50 10 10 10 Returns: 0
It is not possible to record 50 songs if each Vocaloid can only sing 10 of them.
3)
18 12 8 9 Returns: 81451692
4)
50 25 25 25 Returns: 198591037
Submissions are judged against all 70 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class VocaloidsAndSongs with a public method int count(int S, int gumi, int ia, int mayu) · 70 test cases · 2 s / 256 MB per case