Problem Statement
There is a long circular one-way road. Along the road there are N parking spots, numbered from 0 to N-1 in order. As you drive along the road, parking spot numbers increase (and after N-1 you get back to 0).
Initially, all parking spots are empty. N cars arrive to the circular road and park there. The cars arrive one at a time: the next car always arrives only after the previous one has parked.
The cars are numbered from 0 to N-1 in the order in which they arrive. The numbering of cars is unrelated to the numbering of parking spots.
Different cars may enter the circular road at different locations. For each car i, let P[i] be the first parking spot it will encounter. The sequence P will be called a parking sequence.
There are N^N different parking sequences.
Each car drives along the road until it finds an empty parking spot. Once it finds an empty parking spot, it parks there.
For example, if we have N = 4 and the parking sequence {3, 2, 2, 3}, car 0 will park at spot 3, car 1 will park at spot 2, car 2 will drive past occupied spots 2 and 3 and park at spot 0, and finally car 3 will drive past occupied spots 3 and 0 and park at the final free spot 1.
Each time a car encounters an occupied parking spot, a collision occurs. We don't like collisions, as they cause delays. The badness of a parking sequence is the number of collisions it causes.
For example, the above parking sequence {3, 2, 2, 3} has badness 4.
Let C(X,Y) be the number of parking sequences for X cars and X parking spots such that during the parking there are exactly Y collisions.
You are given N and B. Calculate and return C(N,B) mod 1,000,000,007.
Definition
- Class:
- ParkingSequences
- Method:
- count
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int count(int N, int B)
- (be sure your method is public)
Constraints
- N will be between 1 and 50, inclusive.
- B will be between 0 and N*(N-1)/2, inclusive.
- B will not exceed 200.
Examples
4
6
Returns: 4
In order to have the maximum number of collisions, all cars have to arrive at the same place. Each car will then drive along all previously-parked cars until it reaches an empty parking spot. Thus, the parking sequences we seek are the sequences {0,0,0,0}, {1,1,1,1}, {2,2,2,2}, and {3,3,3,3}.
13
0
Returns: 227020758
In order to have no collisions at all, each car must arrive at a different parking spot. Thus, the parking sequences we are counting in this example are permutations of order N. The return value equals 13! modulo (10^9 + 7).
4
1
Returns: 48
Two of these parking sequences: {0,0,2,3}: the collision is car 1 passing by car 0 parked on the spot 0 {1,2,2,0}: car 0 parks on the spot 1, car 1 parks on the spot 2, car 2 arrives at spot 2 (collision), continues to the empty spot 3 and parks there. Then, the final car arrives at spot 0 and parks there.
5
9
Returns: 25
In order to have exactly one fewer collisions than the theoretical maximum, each car must start at the same spot, except for one car that will start one spot further along the road. For example, {4, 4, 4, 0, 4} is one of these parking sequences.
1
0
Returns: 1
2
0
Returns: 2
2
1
Returns: 2
50
200
Returns: 418216602
5
0
Returns: 120
5
1
Returns: 300
5
2
Returns: 450
5
3
Returns: 550
5
4
Returns: 600
5
5
Returns: 500
5
6
Returns: 325
5
7
Returns: 175
5
8
Returns: 75
5
10
Returns: 5
11
48
Returns: 213928
12
56
Returns: 4232592
11
3
Returns: 445320793
18
37
Returns: 220139791
8
15
Returns: 502656
18
116
Returns: 318015404
16
38
Returns: 545358134
6
4
Returns: 6300
13
17
Returns: 915105214
18
18
Returns: 155128392
6
12
Returns: 336
20
99
Returns: 71269594
9
36
Returns: 9
13
29
Returns: 188134651
19
12
Returns: 772313452
7
16
Returns: 3234
13
26
Returns: 597332845
14
29
Returns: 932481063
18
66
Returns: 337307239
11
52
Returns: 3146
9
26
Returns: 390096
13
3
Returns: 534775101
18
73
Returns: 181957074
9
18
Returns: 10243800
12
62
Returns: 16380
8
25
Returns: 960
10
36
Returns: 486100
12
54
Returns: 16223196
16
117
Returns: 13056
11
17
Returns: 243454571
32
28
Returns: 12819435
21
133
Returns: 388034585
26
64
Returns: 683802593
27
25
Returns: 187077811
37
143
Returns: 223254953
30
22
Returns: 143936634
30
2
Returns: 963271154
21
176
Returns: 748139249
23
121
Returns: 801962076
33
136
Returns: 770014365
24
45
Returns: 56629764
24
53
Returns: 544952863
35
65
Returns: 999934007
40
197
Returns: 437473706
31
35
Returns: 629623190
38
165
Returns: 378146855
27
152
Returns: 223011128
38
163
Returns: 435087222
22
170
Returns: 494255166
39
16
Returns: 841295496
36
166
Returns: 367170992
23
23
Returns: 772876685
38
151
Returns: 864330670
37
35
Returns: 630040704
29
162
Returns: 259240363
37
199
Returns: 776380911
36
9
Returns: 676339467
30
154
Returns: 870587702
40
182
Returns: 334453809
25
92
Returns: 586015158
47
185
Returns: 19107624
49
79
Returns: 2867305
49
198
Returns: 924606195
50
187
Returns: 907931470
50
154
Returns: 313332491
50
179
Returns: 629437596
50
157
Returns: 787833575
49
77
Returns: 938539266
48
115
Returns: 181600584
49
12
Returns: 348954306
48
76
Returns: 293248961
48
55
Returns: 723984785
49
17
Returns: 559205074
50
58
Returns: 862168559
49
112
Returns: 609419539
47
130
Returns: 347693086
48
151
Returns: 556663123
50
26
Returns: 310644884
49
4
Returns: 310866371
50
141
Returns: 19010639
49
200
Returns: 717332584
50
50
Returns: 627171105