RabbitNumbering
SRM 463 · 2009-11-12 · by rng_58
SRM 463 · 2009-11-12 · by rng_58 · Math
Problem Statement
Problem Statement
Taro and Hanako have rabbits, and they want to assign a distinct integer to each rabbit so they can easily identify them.
The rabbits have expressed their preferences to Taro and Hanako. The i-th rabbit wants an integer between 1 and maxNumber[i], inclusive. Taro and Hanako must obey the preferences of all their rabbits.
Return the number of ways they can assign numbers to their rabbits, modulo 1,000,000,007. If it's impossible to assign distinct integers to the rabbits, return 0.
The rabbits have expressed their preferences to Taro and Hanako. The i-th rabbit wants an integer between 1 and maxNumber[i], inclusive. Taro and Hanako must obey the preferences of all their rabbits.
Return the number of ways they can assign numbers to their rabbits, modulo 1,000,000,007. If it's impossible to assign distinct integers to the rabbits, return 0.
Constraints
- maxNumber will contain between 1 and 50 elements, inclusive.
- Each element of maxNumber will be between 1 and 1,000, inclusive.
Examples
0)
{5}
Returns: 5
They can assign any number between 1 and 5, inclusive, to the only rabbit.
1)
{4, 4, 4, 4}
Returns: 24
All permutations of {1, 2, 3, 4} are possible.
2)
{5, 8}
Returns: 35
3)
{2, 1, 2}
Returns: 0
4)
{25, 489, 76, 98, 704, 98, 768, 39, 697, 8, 56, 74, 36, 95, 87, 2, 968, 4, 920, 54, 873, 90}
Returns: 676780400
Submissions are judged against all 64 archived test cases, of which 5 are shown here. Case numbers match the judge’s.
Coding Area
Language: C++17 · define a public class RabbitNumbering with a public method int theCount(vector<int> maxNumber) · 64 test cases · 2 s / 256 MB per case