RabbitAndTable | Topcoder Archive

Problem Statement

A group of n rabbits is about to have dinner. For the dinner, they will sit around one or more round tables. They now need to divide themselves into groups that will each share one table.

You know that rabbits are shy. More precisely, you are given the int[] x with n elements. For each valid i, rabbit i wants to sit at a table that has x[i] or fewer rabbits (including rabbit i itself).

Two ways of dividing rabbits into groups are considered different if there is a pair of rabbits that are in the same group in one way and in two different groups in the other way.

Let Z be the number of ways to divide rabbits into groups while respecting all their wishes. Compute and return the value Z modulo (10^9 + 7).

Definition

Class:: RabbitAndTable
Method:: count
Parameters:: int[]
Returns:: int
Method signature:: int count(int[] x)
(be sure your method is public)

Constraints

n will be between 2 and 2,000, inclusive.
x will contain exactly n elements.
Each element in x will be between 1 and n, inclusive.

Examples

```
{3,3,3}
```
```
Returns: 5
```
All rabbits are ok with any number of rabbits in their group, so we have 5 solutions: {0}, {1}, {2} {0, 1}, {2} {0}, {1, 2} {0, 2}, {1} {0, 1, 2}
```
{3,2,3}
```
```
Returns: 4
```
This time one of the rabbits does not want to be in a group of size 3. So this time we only have 4 valid ways to form the groups: {0}, {1}, {2} {0, 1}, {2} {0}, {1, 2} {0, 2}, {1}
```
{1,1,1,1,1,1,1,1,1,1}
```
```
Returns: 1
```
All rabbits are very shy and can only be alone.

{15,15,15,15,15,15,15,15,15,15,15,15,15,15,15}

Returns: 382958538

The answer is 1382958545 % (10^9+7).

```
{3,2,2,1,5,4,4,1,2}
```
```
Returns: 272
```

This problem statement is the exclusive and proprietary property of Topcoder, Inc. Any unauthorized use or reproduction of this information without the prior written consent of Topcoder, Inc. is strictly prohibited. (c)2024, Topcoder, Inc. All rights reserved.