Problem Statement
There are people gangsters in Gangsterville, and that small town definitely isn't big enough for all of them. Therefore they decided to organize a shootout. May only the best survive!
The gangsters arranged themselves in a circle. For simplicity we'll number them from 1 to people along the circle. Each gangster is pointing his gun at the next gangster in the circle. (I.e., for each valid i gangster number i is aiming at gangster number i+1, and the last gangster is aiming at gangster 1.)
In order to make the gunfight more spectator-friendly, the gangsters have decided that they will shoot sequentially. Before the gunfight they will choose one of the people! possible orders uniformly at random. Then, they will shoot their guns in the chosen order. (Obviously, gangsters who have already been shot do nothing when it's their turn.) Each gangster always hits their target.
Calculate the number of orderings for which the number of gangsters who will survive is exactly alive. Return the answer modulo 10^9+7.
Definition
- Class:
- Gangsters
- Method:
- countOrderings
- Parameters:
- int, int
- Returns:
- int
- Method signature:
- int countOrderings(int people, int alive)
- (be sure your method is public)
Constraints
- people will be between 3 and 150, inclusive.
- alive will be between 0 and people, inclusive.
Examples
4
2
Returns: 12
We have four gangsters numbered 1, 2, 3, and 4 along the circle. There are 4! = 24 possible orders in which they will shoot. First consider the six permutations in which gangster 1 shoots first: 1 2 3 4 1 2 4 3 1 3 2 4 1 3 4 2 1 4 2 3 1 4 3 2 In each of these six settings gangster 1 will shoot gangster 2. As gangster 2 will not shoot, gangster 3 is guaranteed to survive. In three of these six setting gangster 3 will shoot before gangster 4. In these three scenarios the survivors will be gangsters 1 and 3. In the other three scenarios gangster 3 will be the only survivor. We can then make similar reasoning for the remaining cases. In total there are 12 orderings with exactly two survivors (and another 12 with just one survivor).
3
1
Returns: 6
There are six possible shooting orders for three gangsters. For all of them only one gangster will remain alive.
3
0
Returns: 0
It is not possible that no one survives.
9
3
Returns: 203616
3
2
Returns: 0
3
3
Returns: 0
4
0
Returns: 0
4
1
Returns: 12
4
3
Returns: 0
4
4
Returns: 0
5
1
Returns: 20
5
2
Returns: 100
5
3
Returns: 0
6
1
Returns: 30
6
2
Returns: 510
6
3
Returns: 180
6
4
Returns: 0
150
0
Returns: 0
150
1
Returns: 22350
150
74
Returns: 449712960
150
75
Returns: 298327036
150
150
Returns: 0
44
11
Returns: 625464479
132
14
Returns: 246806497
48
8
Returns: 221386274
63
13
Returns: 448176929
74
32
Returns: 483436209
141
22
Returns: 621265395
137
41
Returns: 249561047
74
3
Returns: 885520416
73
19
Returns: 785941369
13
3
Returns: 165614592
88
9
Returns: 659224951
34
6
Returns: 926765467
55
27
Returns: 647720112
15
4
Returns: 698999714
96
32
Returns: 432385400
56
15
Returns: 277163265
53
13
Returns: 344727290
32
8
Returns: 443989692
128
25
Returns: 641032416
104
51
Returns: 721782805
118
19
Returns: 430336012
34
7
Returns: 506841146
23
2
Returns: 81010100
49
25
Returns: 0
108
49
Returns: 890690503
14
6
Returns: 956730625
132
3
Returns: 351568247
47
10
Returns: 33620122
129
46
Returns: 679602399
43
8
Returns: 86487190
58
19
Returns: 600000269
123
36
Returns: 806730792
45
14
Returns: 118549538
111
26
Returns: 194493840
8
2
Returns: 7224
31
8
Returns: 652379459
115
32
Returns: 808357575
37
14
Returns: 363746661
73
17
Returns: 520857457
32
7
Returns: 208964088
48
1
Returns: 2256
73
18
Returns: 794039711
33
7
Returns: 457687856
22
11
Returns: 36721329
81
4
Returns: 800646368
43
9
Returns: 504122179
103
49
Returns: 310994297
48
5
Returns: 260712075
39
7
Returns: 534355308
119
60
Returns: 0
30
11
Returns: 256729948
113
32
Returns: 111601008
114
52
Returns: 945354954
82
39
Returns: 301919122
96
13
Returns: 496107025
65
24
Returns: 449026526
60
21
Returns: 639262763
81
40
Returns: 221940159
16
2
Returns: 23593200
13
2
Returns: 1437852
107
16
Returns: 838941142
122
4
Returns: 712265217
40
8
Returns: 950068627
108
53
Returns: 470613649
40
14
Returns: 307400679
89
39
Returns: 270414044
140
55
Returns: 385434859
69
32
Returns: 19555135
87
10
Returns: 749168526
100
20
Returns: 834358364
19
9
Returns: 77589857
109
41
Returns: 108333060
11
4
Returns: 23682120
131
60
Returns: 80839208
83
20
Returns: 163282721
27
6
Returns: 123919043
30
6
Returns: 650286915
150
50
Returns: 351696986