Problem Statement
The black and white chess rooks were bored, so they decided to invite their colorful friends to a party. However, as the evening progressed, many pairs of rooks of different colors started arguing and threatening each other.
To prevent a massacre, you now need to place all the rooks in such a way that no two rooks of different colors attack each other.
You are given the dimensions of the chessboard:
Compute and return the value (X mod 1,000,000,009), where X is the number of valid arrangements of all the given rooks on the given chessboard. No square of the chessboard may contain more than one rook. Rooks of the same color are undistinguishable.
Definition
- Class:
- RooksParty
- Method:
- countArrangements
- Parameters:
- int, int, int[]
- Returns:
- int
- Method signature:
- int countArrangements(int rows, int columns, int[] counts)
- (be sure your method is public)
Notes
- Two rooks attack each other if they are either in the same row or in the same column, and all squares between them are empty.
Constraints
- rows will be between 1 and 30, inclusive.
- columns will be between 1 and 30, inclusive.
- counts will contain between 1 and 10 elements, inclusive.
- Each element of counts will be positive.
- The sum of all elements of counts will not exceed rows*columns.
Examples
2
3
{1,1}
Returns: 12
Here are all 12 valid placements: 1.. 1.. .1. .1. ..1 ..1 .2. ..2 2.. ..2 2.. .2. .2. ..2 2.. ..2 2.. .2. 1.. 1.. .1. .1. ..1 ..1
5
2
{3}
Returns: 120
As all three rooks have the same color, we can put them on any three squares.
5
2
{1,1,1}
Returns: 0
It is impossible to place these rooks correctly.
8
8
{1,1,1,1,1,1,1,1}
Returns: 625702391
Here the answer is (8! * 8!) modulo 1,000,000,009.
8
8
{2,2,2,2}
Returns: 394476764
30
30
{1,1,1,1,1,1,1,1,1,1}
Returns: 468830579
30
30
{1,2,3,4,5,6,7,8,9}
Returns: 935915834
5
5
{2,2,1,1}
Returns: 7200
30
30
{1,841}
Returns: 900
30
30
{397,94}
Returns: 803311538
30
30
{9,9,9,9,9,9,9,9,9,9}
Returns: 267002851
4
2
{3,1}
Returns: 8
29
30
{1,2,3,4,5,6,7,8,9,80}
Returns: 622925491
30
29
{2,3,4,5,6,7,8,9,10,14}
Returns: 363644201
26
29
{1,2,1,3,1,2,1,4,1,2}
Returns: 915225757
1
1
{1}
Returns: 1
2
2
{1,1}
Returns: 4
2
2
{1,2}
Returns: 0
2
2
{1,1,1}
Returns: 0
2
2
{1,3}
Returns: 0
2
2
{3}
Returns: 4
2
2
{4}
Returns: 1
1
7
{1,1}
Returns: 0
7
1
{1,1}
Returns: 0
7
1
{3}
Returns: 35
1
15
{13}
Returns: 105
30
30
{87,367}
Returns: 562387422
30
30
{94,80,96}
Returns: 145737436
30
29
{45,32,37,14}
Returns: 250052181
27
28
{32,41,14,52,23,12}
Returns: 0
27
29
{32,11,14,32,23,12}
Returns: 767323759
27
27
{3,3,3,3,3,3,3,3,3}
Returns: 991794313
27
27
{9,9,9,9,9,9,9,9,9}
Returns: 319751833
27
27
{9,9,9,9,9,9,9,9,9,1}
Returns: 0
13
24
{3,1,4,1,5,9,2,6,5,3}
Returns: 0
17
23
{3,1,4,1,5,9,2,6,5,3}
Returns: 774314182
30
30
{29,28,1}
Returns: 704560351
30
30
{470}
Returns: 290656099
30
19
{ 98,5 }
Returns: 742846778
12
10
{ 5 }
Returns: 190578024
19
15
{ 1,3,1 }
Returns: 453925457
2
20
{ 1,2 }
Returns: 6840
4
30
{ 14,1,2 }
Returns: 767537416
26
2
{ 14 }
Returns: 966328688
15
4
{ 1 }
Returns: 60
26
1
{ 12 }
Returns: 9657700
12
22
{ 2,1,1,2 }
Returns: 863097707
25
29
{ 2,17 }
Returns: 33965938
30
29
{ 7,14,68 }
Returns: 940560931
19
7
{ 3 }
Returns: 383306
13
8
{ 2,1 }
Returns: 362544
20
20
{ 12,3 }
Returns: 230276532
16
16
{ 3,1,1,7 }
Returns: 993895993
22
22
{ 5,7,3 }
Returns: 128104149
13
4
{ 2,4 }
Returns: 20442708
28
14
{ 9,4 }
Returns: 546127733
4
23
{ 6 }
Returns: 713068356
27
19
{ 1,2,10,2 }
Returns: 949183484
12
26
{ 1,3,6 }
Returns: 59838359
23
24
{ 10 }
Returns: 329551174
14
19
{ 9,2,1,1 }
Returns: 106818656
19
28
{ 8,1 }
Returns: 240141622
24
6
{ 8 }
Returns: 79326324
3
5
{ 6 }
Returns: 5005
17
11
{ 2 }
Returns: 17391
23
8
{ 1,1,1 }
Returns: 3570336
10
23
{ 57 }
Returns: 761240178
22
9
{ 6,2 }
Returns: 237115933
2
29
{ 2 }
Returns: 1653
19
7
{ 1,1,1 }
Returns: 1220940
26
15
{ 62 }
Returns: 658858839
11
8
{ 3,18 }
Returns: 227688066
13
10
{ 1,2,1 }
Returns: 53745120
10
9
{ 5 }
Returns: 43949268
16
5
{ 9,5 }
Returns: 628962191
23
5
{ 1,1 }
Returns: 10120
16
12
{ 3,4 }
Returns: 58378339
28
23
{ 7,19,3,1 }
Returns: 743596612
24
22
{ 6,5,98 }
Returns: 740960293
28
27
{ 1,12,1 }
Returns: 564205685
21
23
{ 5 }
Returns: 553076450
21
25
{ 21,2 }
Returns: 34540723
22
21
{ 9,4,36 }
Returns: 564615880
25
27
{ 2,9,3,3 }
Returns: 112135274
22
27
{ 1,23,7 }
Returns: 594842349
21
26
{ 7,4,1 }
Returns: 590092512
26
26
{ 38,18,2 }
Returns: 798583690
28
21
{ 72,145 }
Returns: 843854779
27
29
{ 2,28,15,1 }
Returns: 492933994
29
26
{ 4,4,1,12,1,1 }
Returns: 309289548
25
24
{ 18 }
Returns: 566080194
25
25
{ 1,2,1 }
Returns: 276159550
21
24
{ 57,2,10 }
Returns: 276733073
24
22
{ 4,157,2,3 }
Returns: 192987970
23
22
{ 5,15,1 }
Returns: 342454571
27
22
{ 22,3 }
Returns: 553461418
21
28
{ 8,18,1 }
Returns: 840622781
24
23
{ 2,2,1,4,1,6 }
Returns: 802255234
25
26
{ 6,7,3 }
Returns: 38458654
21
21
{ 24,18 }
Returns: 69650857
25
23
{ 7,5,10 }
Returns: 821972186
25
28
{ 8,6 }
Returns: 498642371
24
23
{ 110,9 }
Returns: 799184574
26
22
{ 15,40 }
Returns: 668257817
27
23
{ 3,1,28,6 }
Returns: 579946758
22
24
{ 11,2,4 }
Returns: 898379985
21
29
{ 1,13,5,66,7 }
Returns: 338245160
30
30
{5, 8, 23 }
Returns: 69418122
30
30
{3, 2, 1, 2, 1, 1, 1, 1, 2, 5 }
Returns: 377470053
30
30
{500 }
Returns: 467129293
30
29
{11, 3, 1, 5, 6, 7, 8, 9, 10, 3 }
Returns: 716270682
30
30
{1 }
Returns: 900
30
30
{4, 4, 4, 4, 4, 4, 4, 4, 4, 4 }
Returns: 67443848
30
29
{16, 12, 4, 9, 6, 1, 3, 2, 1, 25 }
Returns: 451736225
29
29
{8, 11, 123, 12, 234, 123, 11, 12, 35, 12 }
Returns: 0
30
30
{100, 10 }
Returns: 762574528